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,192
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: 198
Website

Re: Problem around modular arithmatic

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

is also a solution to

i.e. to

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

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

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

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: 198
Website

Re: Problem around modular arithmatic

So there you have it:

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: 198
Website

Re: Problem around modular arithmatic

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

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

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

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