Let a be a positive integer. Is it possible for a 3 2 + 1 to be divisible by 2017?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Suppose that a 3 2 + 1 is divisible by 2017, i.e. a 3 2 ≡ − 1 ( m o d 2 0 1 7 ) . We could restrict the possible value of a in the range [ 1 , 2 0 1 6 ] and because 2 0 1 7 is prime we also have g cd ( a , 2 0 1 7 ) = 1 . Note that ϕ ( 2 0 1 7 ) = 2 0 1 6 = 6 3 ∗ 3 2 and, due to Euler's Theorem a 2 0 1 6 ≡ 1 ( m o d 2 0 1 7 ) . But from a 3 2 ≡ − 1 ( m o d 2 0 1 7 ) we also have 1 = a 2 0 1 6 = ( a 3 2 ) 6 3 ≡ ( − 1 ) 6 3 = − 1 ( m o d 2 0 1 7 ) and so 1 ≡ − 1 ( m o d 2 0 1 7 ) which is impossible.
Problem Loading...
Note Loading...
Set Loading...
First, we shall prove that, for any relatively prime positive integers x , y and any positive integer n , any odd prime divisor of x 2 n + y 2 n must have the form 2 n + 1 k + 1 for some positive integer k .
Let p be an odd prime divisor of x 2 n + y 2 n . We have
x 2 n + y 2 n x 2 n ( x y − 1 ) 2 n ( x y − 1 ) 2 n + 1 ≡ 0 ( m o d p ) ≡ − y 2 n ( m o d p ) ≡ − 1 ( m o d p ) ≡ 1 ( m o d p ) .
Note that y − 1 exists because p is a prime and y cannot be divisible by p . If y were divisible by p , then x would also have to be as well, which violates our assumption that x , y were relatively prime.
Let d = ord p ( x y − 1 ) . We have d ∣ 2 n + 1 by what we just derived, and d ∣ p − 1 by FLT. We also have d ∤ 2 n , since otherwise we would have ( x y − 1 ) 2 n ≡ 1 ( m o d p ) , forcing p = 2 , which is not valid. Therefore, d = 2 n + 1 . Since d ∣ p − 1 , this means p = 2 n + 1 k + 1 , and we are done. ■
Now, let's apply this result to the problem. We have x = a , y = 1 , n = 5 . Thus, any odd prime divisor of a 3 2 + 1 is of the form 6 4 k + 1 . However, 6 4 ∤ 2 0 1 6 = 2 0 1 7 − 1 , so 2017 cannot be written in this form. Thus, no values of a satisfy the problem statement.