## relatively prime and independent confusion

If a and 77 are relatively prime, show that for positive integers n, a^(10^n) modulo 77 is independent of n.

I think I don't understand what this statement is asking. a^(10^n) modulo 77 independent of n means that a^(10^n) modulo 77 is always going to be the same or something?

 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target
 Blog Entries: 27 Recognitions: Gold Member Homework Help Science Advisor hi math_grl! (try using the X2 icon just above the Reply box ) i think it means that it depends on a, but not on n
 That's a lot of eye twitching there. Should probably see a doctor. I'm still confused as what the next step is.

## relatively prime and independent confusion

so you must show that only the value of a has any influence in the remainder, and notice that the remainder can change when you change the value of a only, but not qhen you let a fixed and change the value of n

I've tried some approaches, but without success

we may try to prove that if

$$a^{10^n}\equiv\ r\ mod\ 77$$
then
$$a^{10^{n+1}}\equiv\ r\ mod\ 77$$
it implies that
$$r^{10}\equiv\ r\ mod\ 77$$

 Blog Entries: 27 Recognitions: Gold Member Homework Help Science Advisor i'm worried … 210 = 1024 = 23 (mod 77) ≠ 21
 but the above is false, so I'm puzzled
 yes, it is false, but 2^(10^n) = 23 mod 77 always, let me see what I did wrong
 certanly is beeing asked to show that if $$a^{10^n}\equiv\ r\ mod\ 77$$ then $$a^{10^{n+1}}\equiv\ r\ mod\ 77$$ the implication was a wrong arithmetic of mine, in fact it implies $$a^{10^{n+1}}-a^{10^n}\equiv\ 0\ mod\ 77$$ $$a^{10^n}(a^{10^{n+1}-10^n}-1)\equiv\ 0\ mod\ 77$$ $$a^{10^{n+1}-10^n}\equiv\ 1\ mod\ 77$$ and $$10^{n+1}-10^n=10^n(10-1)=9\cdot\ 10^n$$ since the above can be written as $$9\cdot\ 10^n=60k$$ for a natural k $$a^{9\cdot\ 10^n}=a^{60k}\equiv\ 1\ mod\ 77$$ by euler's theorem, if gcd(a,77)=1, since $$\varphi{(77)}=60$$ then $$a^{60k}\equiv\ 1\ mod\ 77$$ and it completes the proof

 Quote by tiny-tim i'm worried … 210 = 1024 = 23 (mod 77) ≠ 21
I think you missed the fact that $$n \in \mathbb{N}$$ so 2100 is not considered.

That's some awesome work there! Thanks.

but I'm concerned by this part...

 Quote by al-mahed $$9\cdot\ 10^n=60k$$ for a natural k
if $$n = 1$$, then what is $$k$$?

 Blog Entries: 27 Recognitions: Gold Member Homework Help Science Advisor hi al-mahed! very nice proof, but in future please don't give a full answer on this forum … a good hint in this case would have been " use Euler's theorem, and the fact that φ(77) = 60 "

 Quote by math_grl That's some awesome work there! Thanks. but I'm concerned by this part... if $$n = 1$$, then what is $$k$$?
yes, sorry for that, it holds for n>1, then all you need to do is to verify n = 1

hi tim, thx!

I'll try to make it a hint next time, but I was puzzled by the problem too.

cheers

 Quote by tiny-tim hi al-mahed! very nice proof, but in future please don't give a full answer on this forum … a good hint in this case would have been " use Euler's theorem, and the fact that φ(77) = 60 "

 Quote by tiny-tim a good hint in this case would have been " use Euler's theorem, and the fact that φ(77) = 60 "
so how come that wasn't your original hint, winkie?

Blog Entries: 27
Recognitions:
Gold Member
Homework Help
 Quote by math_grl so how come that wasn't your original hint, winkie?
uhh?

you didn't ask for a hint …

you only asked what the question meant
which i (correctly) told you!

al-mahed, interesting to note is the relation between the terms and functions associated with the topic of this thread (and your observations in relation to it) and Ramanujan's partition number congruences (since 10 is both the totient of 11 and equal to 2 * 5), which have recently been in the news in relation to the break-through of Ken Ono et al.
Ken Ono cracks partition number mystery

To avoid confusion, denote par_n as the n-th partition number. Then Ramanujan's congruences are...

par_(5k+4) == 0 (mod 5)
par_(7k+5) == 0 (mod 7)
par_(11k+6) == 0 (mod 11)
http://en.wikipedia.org/wiki/Ramanujan%27s_congruences
Note: 5, 7 & 11 are the 4th, 5th & 6th partition numbers and because they are all also prime (totient p) = (p-1), then their totient product: totient (5)*totient (7)*totient (11) = 240 = totient (5*7*11)

We can, in relation to your prior posting...
 Quote by al-mahed $$a^{9\cdot\ 10^n}=a^{60k}\equiv\ 1\ mod\ 77$$
...observe that...

par_(totient (77) + (1 + 77n)) = par_(60 + (1 +77n)) = par_(61 +77n) == par(7k+5) and par(11k+6)

Note #1: totient (61) = totient (77) = 60, while 5 & 6 are the partition index numbers of, respectively, 7 & 11, which multiply to 77

Note #2: A CURIO ((totient 9 * totient 10) * (totient (9 * 10))) * ((totient 60 * totient 77) * (totient (60 * 77))) = (24^2)*(40^2*24^2) = 23040^2 = 530841600
530841600 = (x(x+ceiling(2^x/12)))^2*(y(y+ceiling(2^y/12)))^2 = 24^2 * 960^2 for x = totient(5), y = totient(11) See: http://oeis.org/A029929, which for n = 1 through 8, returns proven (lattice) sphere packings to D = 8
530841600 --> the maximal number of divisors of any 40 digit number (http://oeis.org/A066150), and 40 = totient (p_13) = totient p_(p_6)

e.g
par_61= 1121505 = 3 * 5 * 7 * 11 * 971 = par_(60 + (1 mod 77))
par_138 = 12292341831 = 3^2 * 7^2 * 11 * 733 * 3457
par_215 = 14070545699287 = 7^2 * 11^2 * 23497 * 100999
par_292 = 5234371069753672 = 2^3 * 7^2 * 11 * 97 * 223 * 56118901
http://www.asahi-net.or.jp/~KC2H-MSM...1/matha145.htm

... and the original mathematical statement that begins this thread...

a^(10^n) modulo 77 is independent of n

... can be restated as either:

a^((totient 11)^n) modulo (7*11) is independent of n
or...
a^((2*5)^n) modulo (7*11) is independent of n

2400 = totient (5*7) * (totient (11))^2 = totient (35) * (totient (11))^2 = 24 * 10^2
2400 = totient (5*11) * totient (7*11) = totient (55) * totient (77) = 40 * 60
2400 = totient(11)*totient(5*7*11) = totient(11)*totient(385) = 10 * 240

2400 can be restated in terms of partition numbers as...
totient (par_4) * totient (par_5)* totient(par_(p_6))= totient (par_4) * totient (par_5)* totient(par_13) = totient (5) * totient (7)* totient(101) = 4*6*100 = 2400
Note: Recall that 4, 5, & 6 are the partition index numbers associated with 5, 7 and 11

Not sure how one might more explicitly relate the topic of this thread with partitions, but it seems at least an interesting question to to think about. (I won't even get into the myriad possible connections one might make in relation to sphere packings...)

- RF

P.S. Also note A) that par (369 + 385(n)) == par(5k+4), par(7k+5) and par(11k+6), where 385 (=5*7*11) is the sum of squares of 0 --> 10 and 369 is not only 3^1* the 10th Lucas Number, but also 3^2* the 13th (or p_6th) prime = 41, and B) just as totient 61 = totient 77 = 60, totient 369 = totient 385 = 240

P.P.S. A surprising relationship (to me, at least)...
par_61 = par_(60 + (1 mod 77)) = p_2 * p_3 * p_4 * p_5 * p_(4*p_(p_6)) = 3 * 5 * 7 * 11 * p_(4*41) = 3 * 5 * 7 * 11 * 971 = 1121505
Note: 4 = totient 5 = 5-1, & 6 = totient 7 = 5+1

 that's an interesting stuff, but could you clarify what you're saying here: par_(totient (77) + (1 + 77n)) = par_(60 + (1 +77n)) = par_(61 +77n) == par(7k+5) and par(11k+6) are you saying 1) $$par(61 +77n) \equiv\ par(7k+5) + par(11k+6)\ mod\ 77$$ or 2) $$par(61 +77n) \equiv\ par(7k+5)*par(11k+6)\ mod\ 77$$ ? about the problem itself I wonder how it could deal with the case n=1...? what I was thinking right now was to use the fact there is no primitive root mod pq, hence mod 77, so a^k-1 would be always true for some divisors k of 60 depending on the value of a, so the following step would be to prove that either 90 do the trick or not (and in fact it does) notice that 90 ==> 30, and it leaves out the case = 4, ALL other cases work with 30 obs: that's easy to see, since 60 is always true, 30 is certanly true for all cases but 4 as gcd(30,4)=2, so as gcd(90,4)=2, whatever 30 or 90, all we have to do is to check the remainders r^4 == 1 mod 77 so all you have to do is to notice that the remainders 1, 34, 43, 76 are congruent to 1 when the exponent is 4, of course lets trow out 1 (Mod 77) 34^4 == 1 43^4 == 1 76^4 == 1 but suprinsingly (Mod 77) 34^30 == 1 43^30 == 1 76^30 == 1 that's very easy and fast using a good software (I use PARI, Greathouse's suggestion), but I wonder how to prove it by pencil and paper