Sweet 17

Number Theory Level 3

Let $x$ be any positive integer greater than $17^{17}$ , which is not divisible by $17$ .

Then which of the following is always true :

A: either $x^8-1$ , or $x^8+1$ , is divisible by $17$ .

B: either $x^9-1$ , or $x^9+1$ , is divisible by $17$ .

C: either $x^8-1$ , or $x^9+1$ , is divisible by $17$ .

D: either $x^8+1$ , or $x^9-1$ , is divisible by $17$ .

D C A B

1 solution

Danish Ahmed
Jan 15, 2015

The answer is $A$ .

let the number be $x = 17k+r$ with $1<=r<=16$ then $(17k+r)^8$ mod $17$ is congruent to $r^8$ mod $17$ now for $r=1$ through $16$ , $r^8$ mod $17$ is either $1$ or $16$ (easily verified by direct calculation)

$r$ : $r^8$ mod $17$

1 : 1

2 : 1

3 : 16

4 : 1

5 : 16

6 : 16

7 : 16

8 : 1

9 : 1

10 : 16

11 : 16

12 : 16

13 : 1

14 : 16

15 : 1

16 : 1

thus in every case either $r^8-1$ or $r^8-1$ is congruent to $0$ mod $17$ , thus in every case either $x^8+1$ or $x^8-1$ is divisible by $17$

$\displaystyle 17|x^{16}-1=(x^8+1)(x^8-1)$ .

Satvik Golechha - 6 years, 4 months ago

By Fermat's little theorem, yes :)

Jake Lai - 6 years, 4 months ago

That's how I solved it ^^.

Sudeshna Pontula - 6 years, 4 months ago

Sweet 17

1 solution

0 pending reports