Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2018-01-01 01:43:01

Abbas0000
Member
Registered: 2017-03-18
Posts: 29

Problem around modular arithmatic

Solve for x ;
10^n+10^n-1+10^n-2+...+10^1+1 congruent to 0 (mod 59)

Offline

#2 2018-01-01 01:44:40

Abbas0000
Member
Registered: 2017-03-18
Posts: 29

Re: Problem around modular arithmatic

I'm sorry that was (solve for n)

Offline

#3 2018-01-01 02:18:03

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: Problem around modular arithmatic

The LHS is the sum of (n+1) terms of a geometric sequence with common ratio 10. What happens when you simplify it?

Offline

#4 2018-01-01 02:22:49

Alg Num Theory
Member
Registered: 2017-11-24
Posts: 693
Website

Re: Problem around modular arithmatic

Since 59 and 9 = 10 − 1 are coprime, any solution to

[list=*]
[*]

[/*]
[/list]

is also a solution to

[list=*]
[*]

[/*]
[/list]

i.e. to

[list=*]
[*]

[/*]
[/list]

and vice versa. By Fermat’s little theorem, as 59 is prime,

[list=*]
[*]

[/*]
[/list]

Therefore the smallest positive value of n+1 must divide 58. Clearly 10 ≢ 1 (mod 59) and 10² = 100 ≢ 1 (mod 59). If you can show that

[list=*]
[*]

[/*]
[/list]

then n+1 will be a multiple of 58 and the general solution will be n = 58k − 1, k = 1, 2, 3, ….


Me, or the ugly man, whatever (3,3,6)

Offline

#5 2018-01-01 02:37:06

Abbas0000
Member
Registered: 2017-03-18
Posts: 29

Re: Problem around modular arithmatic

Thanks but what was fermat's little theorem and how you conclude n+1=58 by that?

Offline

#6 2018-01-01 02:38:50

Alg Num Theory
Member
Registered: 2017-11-24
Posts: 693
Website

Re: Problem around modular arithmatic

So there you have it:

[list=*]
[*]

[/*]
[/list]


Me, or the ugly man, whatever (3,3,6)

Offline

#7 2018-01-01 02:48:55

Abbas0000
Member
Registered: 2017-03-18
Posts: 29

Re: Problem around modular arithmatic

I still can't understand how you've found n+1=58 in step 3 and 4

Offline

#8 2018-01-01 02:58:15

Abbas0000
Member
Registered: 2017-03-18
Posts: 29

Re: Problem around modular arithmatic

If you have multiplied 10^29 by 10^29 than ok. But how we should know to find 10^29 and than result its congruent to -1 in mod 59 and THEN multiply it by it-self to find out this answer?

Offline

#9 2018-01-01 06:42:55

Alg Num Theory
Member
Registered: 2017-11-24
Posts: 693
Website

Re: Problem around modular arithmatic

Let me put this in that language of group theory. We have

[list=*]
[*]

[/*]
[/list]

because 58 is the order of G, the multiplicative group of nonzero integers modulo 59 (a prime). If

[list=*]
[*]

[/*]
[/list]

then m must be a multiple of r, the order of 10 in the group G. Now r must be a divisor of the group order |G| = 58, i.e. its possible values are 1, 2, 29, 58. In my posts above, I eliminated 1, 2, 29. Therefore r = 58 (i.e. 10 is generator of the cyclic group G).


Me, or the ugly man, whatever (3,3,6)

Offline

#10 2018-01-03 00:56:52

Abbas0000
Member
Registered: 2017-03-18
Posts: 29

Re: Problem around modular arithmatic

Thanks again but another question: how can we find the group order because in the answer above,you mentioned it's 58 but how did you measured it before finding the answer?((sorry for asking a lot wink ))

Offline

Board footer

Powered by FluxBB