Modulo Question

[Monkmonk]

Find the least k such that 3^k mod k ≡ 24

Please explain the method

[THEMOTLEY1]

Did you mean: Find the least k such that 3^n mod k ≡ 24

[Monkmonk]

Sorry THEMOTLEY1 I do mean what I wrote:

Find the least k such that 3^k mod k ≡ 24

[fiction-factory]

I remember we had to do mod problems at primary school as some sort of modern maths experiment and then I never did it again until university. I'm very rusty on this but I've tried several integer values for k up to 23 and never got a value greater than 3. I can't see how it could ever ≡ 24 but will think again later

[Monkmonk]

Thanks for looking fiction-factory but it is clear that k must be more than 24 else how could the answer mod k be 24? Trying values for k up to 23 was certain to fail.

[fiction-factory]

5559060566555520 mod 33 = 24

[fiction-factory]

3^33 mod 33 ≡ 24

[fiction-factory]

I said I was a bit rusty

[jim360]

Yes but that's not 3^33 (3^33 Mod 33 is actually 27). 3^n ends in 3, 9, 7, 1 in that order, rotating every four trials.

As monkmonk says, k had to be greater than 24 to start with. It also has to be odd, as any even k would give an odd remainder. In fact I reckon the smallest k, based on exhaustive searching (thank you Mathematica gods) is k=721. I'm trying to figure out what the method is as we speak.

[fiction-factory]

Yes, my spreadsheet seems to start rounding once it gets beyond 3 ^31

[Monkmonk]

I am fairly sure that the answer is k = 721 but I don't know how to prove it.

[jim360]

Just before I spend too much time on this, what was the context of the question?

[Monkmonk]

jim360 read this month's Magpie editorial

[Peter Pedant]

Hi jim
you have a readership of two ( me as well )

so if you have any wise words then I would read them

basically so far we have a British Museum approach of trying every odd power until you find one ?

also I observe that 3 divides 24 and also the answer 721
would that shorten the search ?

( I feel so well after my crappy time at the Christie that I am restarting D Burtons Elem No Theory )

[jim360]

Huh. I'd read that before but I'd forgotten about it.

Anyway, so far as I can see it has to be essentially trial and error to find the right answer, although there are a few ways to reduce the parameter space:

- k is odd.
- k is greater than 24.
- k is not prime (this is based on Fermat's last Theorem that states if p is prime then a^p mod p = a).
- k is not divisible by 9 (this is currently just Engineers' induction, but 3^(9n) mod 9n appears to produce a result that is always itself divisible by 9. I don't know if there's a way to see this automatically. Probably it's obvious really).

I think this reduces the parameter space (for odd numbers below 100) to, say,

25 33 35 39 49 51 55 57 65 69 75 77 85 87 91 93

which is at least only 16 numbers to test, rather than 100. They'll all come up short though, and indeed you have to press on to 721. With Mathematica I'm able to test thousands of numbers at once (and don't even have to look carefully), and it seems that 721 is the only answer that works up to 100,000 (trying to test up to a million, taking a little longer than hoped).

My suspicion is that you probably have to know how to program this, as I'm not seeing any obvious patterns. In particular, while most of the time the answer to 3^k mod k is divisible by 3, sometimes it is not -- the numbers for which this result fails are 49, 85, 115, 125, 133, 145, 169, 175, 185, 205, 215, 217 ...

I'm coming up short at the moment for a general method. There are ways to reduce the difficulty of the computation as, for example, 3^721 mod 721 is the same thing as ((3^300 mod 721)*(3^421 mod 721) )mod 721, or ((3^200 mod 721)*(3^521 mod 721) )mod 721, so that you can reduce the computation difficulty a little.

Just be grateful that you weren't asked to find (by hand) the least value k for which 3^k mod k = 26 (which is 4343), or =29 (25,517 and then 46,891).

[Peter Pedant]

god thx jim
I can see why you are a don and I scrape around a kitchen in a suburban semi
are you sure you dont want to retrain as a barrrister ?

[Monkmonk]

jim360, I think the least answer to 3^k mod k ≡ 29 is not 25,517 but 2270

[jim360]

Actually it's 52 (also 130 works) -- but you are right, it's lower than 25,517, sorry about that! I'd forgotten to turn off the "ignore even numbers" condition in my code so missed all the lower solutions.

But anyway. So far as I can tell this is a problem that requires serious computing rather than a hand-based approach. One reason for this might be that it is in some ways related to problems such as RSA encryption and Integer factorisation that are known to be super-hard (at least until Quantum Computing gets off the ground.

[Monkmonk]

Indeed 52, 130 and 2270 are the first 3 answers to 3^k mod k ≡ 29.
It is tricky to find a general method. However I suspect there is something better than a computer search.

[jim360]

I'm asking around -- although, as I say, this is related to problems that don't yield to anything other than a computer search, so apart from some useful reductions due to Fermat's Little Theorem I suspect it's a case of squeezing the number of cases you have to try as far as possible then exhaustive searching.

Having said that, for each k there is a cycle related to the prime factorisation, so I think that means that it's sufficient at least to test 3^n for values of n up to the largest prime factor of k. More study needed.