To the 32nd power!

Let a a be a positive integer. Is it possible for a 32 + 1 a^{32} + 1 to be divisible by 2017?

Yes, for finitely many a a Yes, for infinitely many a a No

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.

2 solutions

Steven Yuan
Aug 23, 2017

First, we shall prove that, for any relatively prime positive integers x , y x, y and any positive integer n , n, any odd prime divisor of x 2 n + y 2 n x^{2^n} + y^{2^n} must have the form 2 n + 1 k + 1 2^{n + 1}k + 1 for some positive integer k . k.

Let p p be an odd prime divisor of x 2 n + y 2 n . x^{2^n} + y^{2^n}. We have

x 2 n + y 2 n 0 ( m o d p ) x 2 n y 2 n ( m o d p ) ( x y 1 ) 2 n 1 ( m o d p ) ( x y 1 ) 2 n + 1 1 ( m o d p ) . \begin{aligned} x^{2^n} + y^{2^n} &\equiv 0 \! \! \! \! \pmod{p} \\ x^{2^n} &\equiv -y^{2^n} \! \! \! \! \pmod{p} \\ (xy^{-1})^{2^n} &\equiv -1 \! \! \! \! \pmod{p} \\ (xy^{-1})^{2^{n + 1}} &\equiv 1 \! \! \! \! \pmod{p}. \end{aligned}

Note that y 1 y^{-1} exists because p p is a prime and y y cannot be divisible by p . p. If y y were divisible by p , p, then x x would also have to be as well, which violates our assumption that x , y x, y were relatively prime.

Let d = ord p ( x y 1 ) . d = \text{ord}_p(xy^{-1}). We have d 2 n + 1 d|2^{n + 1} by what we just derived, and d p 1 d|p - 1 by FLT. We also have d 2 n , d \nmid 2^n, since otherwise we would have ( x y 1 ) 2 n 1 ( m o d p ) , (xy^{-1})^{2^n} \equiv 1 \! \pmod{p}, forcing p = 2 , p = 2, which is not valid. Therefore, d = 2 n + 1 . d = 2^{n + 1}. Since d p 1 , d|p - 1, this means p = 2 n + 1 k + 1 , p = 2^{n + 1}k + 1, and we are done. \blacksquare

Now, let's apply this result to the problem. We have x = a , y = 1 , n = 5. x = a, y = 1, n = 5. Thus, any odd prime divisor of a 32 + 1 a^{32} + 1 is of the form 64 k + 1. 64k + 1. However, 64 2016 = 2017 1 , 64 \nmid 2016 = 2017 - 1, so 2017 cannot be written in this form. Thus, no values of a a satisfy the problem statement.

Alex Hack
Apr 4, 2019

Suppose that a 32 + 1 a^{32}+1 is divisible by 2017, i.e. a 32 1 ( m o d 2017 ) a^{32}\equiv -1\pmod{2017} . We could restrict the possible value of a a in the range [ 1 , 2016 ] [1,2016] and because 2017 2017 is prime we also have gcd ( a , 2017 ) = 1 \gcd(a,2017)=1 . Note that ϕ ( 2017 ) = 2016 = 63 32 \phi(2017)=2016=63*32 and, due to Euler's Theorem a 2016 1 ( m o d 2017 ) a^{2016}\equiv 1\pmod{2017} . But from a 32 1 ( m o d 2017 ) a^{32}\equiv -1\pmod{2017} we also have 1 = a 2016 = ( a 32 ) 63 ( 1 ) 63 = 1 ( m o d 2017 ) 1= a^{2016}=(a^{32})^{63}\equiv (-1)^{63}=-1\pmod{2017} and so 1 1 ( m o d 2017 ) 1\equiv -1\pmod{2017} which is impossible.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...