Problem around modular arithmatic

Abbas0000 · 2018-01-01 01:43:01

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

Abbas0000 · 2018-01-01 01:44:40

I'm sorry that was (solve for n)

zetafunc · 2018-01-01 02:18:03

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

Alg Num Theory · 2018-01-01 02:22:49

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

Abbas0000 · 2018-01-01 02:37:06

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

Alg Num Theory · 2018-01-01 02:38:50

So there you have it:

[list=*]
[*]

[/*]
[/list]

Abbas0000 · 2018-01-01 02:48:55

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

Abbas0000 · 2018-01-01 02:58:15

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?

Alg Num Theory · 2018-01-01 06:42:55

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

Abbas0000 · 2018-01-03 00:56:52

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

Math Is Fun Forum

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

Problem around modular arithmatic

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

Re: Problem around modular arithmatic

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

Re: Problem around modular arithmatic

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

Re: Problem around modular arithmatic

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

Re: Problem around modular arithmatic

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

Re: Problem around modular arithmatic

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

Re: Problem around modular arithmatic

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

Re: Problem around modular arithmatic

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

Re: Problem around modular arithmatic

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

Re: Problem around modular arithmatic

Board footer