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

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

 

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

 

[math_grl]

i'm worried …

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

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

 

[math_grl]

That's some awesome work there! Thanks.

but I'm concerned by this part...

9\cdot\ 10^n=60k for a natural k

if n = 1, then what is k?

 

[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]

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

 

[al-mahed]

hi tim, thx!

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

cheers

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 "

 

[math_grl]

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?

 

[tiny-tim]

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! ​

 

[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
https://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's_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...

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/mathland/matha1/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) 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 let's 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

 

[Raphie]

Here again are the examples I gave...

par_61= 1121505 = 3 * 5 * 7 * 11 * 971
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

All that I was saying, al-mahed, is that for every (61 + 77n)-th partition number, then (of 5, 7 & 11...) 7 and 11 will divide that number (which does not exclude other partition numbers having all 3 as factors, as is evident for par_61), just as for every (369 + 385n)-th partition number, then 5, 7 and 11 will divide it.RF

 

[spamiam]

Hello!

I think it's worth noting that in al-mahed's proof, he implicitly uses the fact that a (and therefore also a¹⁰ⁿ) is invertible in Z/77Z. Otherwise a^{10^n}(a^{10^{n+1}-10^n}-1)\equiv\ 0\ mod\ 77
would not necessarily imply
a^{10^{n+1}-10^n}\equiv\ 1\ mod\ 77.

since Z/77Z is not an integral domain.

 

[al-mahed]

Hello!

I think it's worth noting that in al-mahed's proof, he implicitly uses the fact that a (and therefore also a¹⁰ⁿ) is invertible in Z/77Z. Otherwise a^{10^n}(a^{10^{n+1}-10^n}-1)\equiv\ 0\ mod\ 77
would not necessarily imply
a^{10^{n+1}-10^n}\equiv\ 1\ mod\ 77.

since Z/77Z is not an integral domain.

I must confess I'm still studying abstract algebra, but I think I understand what you're saying, I'm assuming the problem initial hipothesis is true, and it is true since yields euler's totient function at the end of the day (for n>1), and it is true for n=1 by the verification via PARI aid.

Anyway, the problem hipothesis to mod 77 is in fact that it is invertible in Z/77Z, is that the correct interpretation? but for numbers of the form a^(10^n), since you can replace a^(10^n) by a^(10^{n+1})

 

[al-mahed]

just to add that I put this question in a math onlympiad forum and someone gave a much faster, easier and better answer, though the first part complete my proof

a^6\equiv\ 1\ mod\ 7 \ ==>\ (a^6)^{15}=a^{90}\equiv\ 1\ mod\ 7

a^{10}\equiv\ 1\ mod\ 11 \ ==>\ (a^{10})^{9}=a^{90}\equiv\ 1\ mod\ 11

a^{90}\equiv\ 1\ mod\ 77

so

a^{100}\equiv\ a^{10}\ mod\ 77

just use induction via ^10

a^{1000}\equiv\ a^{100}\equiv\ a^{10}\ mod\ 77

so a^{1000}\equiv\ a^{10}\ mod\ 77, etc

 

[math_grl]

a^6\equiv\ 1\ mod\ 7 \ ==>\ (a^6)^{15}=a^{90}\equiv\ 1\ mod\ 7

a^{10}\equiv\ 1\ mod\ 11 \ ==>\ (a^{10})^{9}=a^{90}\equiv\ 1\ mod\ 11

a^{90}\equiv\ 1\ mod\ 77

Not questioning the validity, but where do they get that last line from?

 

[Landau]

If a=b (mod p) and a=b (mod q) with p and q coprime, then a=b (mod pq). This is used with a=a^90, b=1, p=7, q=11.

This result is based on the fact that if p and q are coprime and both p and q divide x, then their product pq also divides x. (This is easily seen to be true, for example, by considering the prime factorization of x. Alternatively: p,q coprime implies cp+dq=1 for some integers c,d. That p and q divide x implies up=x=vq for some integers u,v. Hence
x=x(cp+dq)=cxp+dxq=c(vq)p+d(up)q=pq(cv+du), i.e. pq divides x.)