relatively prime and independent confusion

math_grl

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?

tiny-tim

hi math_grl!

(try using the X² icon just above the Reply box )

i think it means that it depends on a, but not on n

math_grl

That's a lot of eye twitching there. Should probably see a doctor.

I'm still confused as what the next step is.

al-mahed

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

[tex]a^{10^n}\equiv\ r\ mod\ 77[/tex]
then
[tex]a^{10^{n+1}}\equiv\ r\ mod\ 77[/tex]
it implies that
[tex]r^{10}\equiv\ r\ mod\ 77[/tex]

tiny-tim

i'm worried …

2¹⁰ = 1024 = 23 (mod 77) ≠ 2¹

al-mahed

but the above is false, so I'm puzzled

al-mahed

yes, it is false, but 2^(10^n) = 23 mod 77 always, let me see what I did wrong

al-mahed

certanly is beeing asked to show that

if [tex]a^{10^n}\equiv\ r\ mod\ 77[/tex]
then
[tex]a^{10^{n+1}}\equiv\ r\ mod\ 77[/tex]

the implication was a wrong arithmetic of mine, in fact it implies


[tex]a^{10^{n+1}}-a^{10^n}\equiv\ 0\ mod\ 77[/tex]
[tex]a^{10^n}(a^{10^{n+1}-10^n}-1)\equiv\ 0\ mod\ 77[/tex]
[tex]a^{10^{n+1}-10^n}\equiv\ 1\ mod\ 77[/tex]
and [tex]10^{n+1}-10^n=10^n(10-1)=9\cdot\ 10^n[/tex]
since the above can be written as [tex]9\cdot\ 10^n=60k[/tex] for a natural k

[tex]a^{9\cdot\ 10^n}=a^{60k}\equiv\ 1\ mod\ 77[/tex]

by euler's theorem, if gcd(a,77)=1, since [tex]\varphi{(77)}=60[/tex] then

[tex]a^{60k}\equiv\ 1\ mod\ 77[/tex]

and it completes the proof

math_grl

I think you missed the fact that [tex]n \in \mathbb{N}[/tex] so 2¹⁰⁰ is not considered.

math_grl

That's some awesome work there! Thanks.

but I'm concerned by this part...

if [tex]n = 1[/tex], then what is [tex]k[/tex]?

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 "

al-mahed

yes, sorry for that, it holds for n>1, then all you need to do is to verify n = 1

al-mahed

hi tim, thx!

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

cheers

math_grl

so how come that wasn't your original hint, winkie?

tiny-tim

uhh?

you didn't ask for a hint …

you only asked what the question meant …

which i (correctly) told you!

Raphie

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
http://www.physicsforums.com/showthread.php?t=465696

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...
...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

al-mahed

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) [tex]par(61 +77n) \equiv\ par(7k+5) + par(11k+6)\ mod\ 77[/tex]

or

2) [tex]par(61 +77n) \equiv\ par(7k+5)*par(11k+6)\ mod\ 77[/tex]


?

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