- #1

math_grl

- 49

- 0

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?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter math_grl
- Start date

- #1

math_grl

- 49

- 0

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?

- #2

tiny-tim

Science Advisor

Homework Helper

- 25,838

- 256

(try using the X

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

- #3

math_grl

- 49

- 0

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

- #4

al-mahed

- 262

- 0

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]

- #5

tiny-tim

Science Advisor

Homework Helper

- 25,838

- 256

i'm worried …

2^{10} = 1024 = 23 (mod 77) ≠ 2^{1}

2

- #6

al-mahed

- 262

- 0

but the above is false, so I'm puzzled

- #7

al-mahed

- 262

- 0

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

- #8

al-mahed

- 262

- 0

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

- #9

math_grl

- 49

- 0

i'm worried …

2^{10}= 1024 = 23 (mod 77) ≠ 2^{1}

I think you missed the fact that [tex]n \in \mathbb{N}[/tex] so 2

- #10

math_grl

- 49

- 0

but I'm concerned by this part...

[tex]9\cdot\ 10^n=60k[/tex] for a natural k

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

- #11

tiny-tim

Science Advisor

Homework Helper

- 25,838

- 256

very nice proof, but in future

a good hint in this case would have been " use Euler's theorem, and the fact that φ(77) = 60 "

- #12

al-mahed

- 262

- 0

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

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

- #13

al-mahed

- 262

- 0

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

cheers

very nice proof, but in futurepleasedon'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 "

- #14

math_grl

- 49

- 0

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?

- #15

tiny-tim

Science Advisor

Homework Helper

- 25,838

- 256

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

uhh?

you didn't

you only asked

which i (correctly) told you!

- #16

Raphie

- 151

- 0

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

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

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

We can, in relation to your prior posting...

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

...observe that...

par_(totient (77) + (1 + 77n)) =

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

... can be restated as either:

or...

2400 = totient (

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

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

P.P.S. A surprising relationship (to me, at least)...

Last edited:

- #17

al-mahed

- 262

- 0

par_(totient (77) + (1 + 77n)) =

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

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

- #18

Raphie

- 151

- 0

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.

Best,

RF

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.

Best,

RF

Last edited:

- #19

spamiam

- 360

- 0

I think it's worth noting that in al-mahed's proof, he implicitly uses the fact that a (and therefore also a

would not necessarily imply

[tex]a^{10^{n+1}-10^n}\equiv\ 1\ mod\ 77[/tex].

since Z/77Z is not an integral domain.

- #20

al-mahed

- 262

- 0

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

would not necessarily imply

[tex]a^{10^{n+1}-10^n}\equiv\ 1\ mod\ 77[/tex].

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})

- #21

al-mahed

- 262

- 0

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

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

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

so

[tex] a^{100}\equiv\ a^{10}\ mod\ 77[/tex]

just use induction via ^10

[tex] a^{1000}\equiv\ a^{100}\equiv\ a^{10}\ mod\ 77[/tex]

so [tex] a^{1000}\equiv\ a^{10}\ mod\ 77[/tex], etc

- #22

math_grl

- 49

- 0

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

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

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

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

- #23

Landau

Science Advisor

- 905

- 0

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

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

Last edited:

Share:

- Last Post

- Replies
- 1

- Views
- 565

- Last Post

- Replies
- 5

- Views
- 560

- Replies
- 2

- Views
- 147

- Last Post

- Replies
- 32

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 616

- Replies
- 3

- Views
- 1K

- Last Post

- Replies
- 10

- Views
- 843

- Last Post

- Replies
- 12

- Views
- 841

- Last Post

- Replies
- 8

- Views
- 958

- Last Post

- Replies
- 0

- Views
- 618