Im stumped on this problem, please help!! Math numbers...?

Question

if x^65535 -1 is divisible by the prime number 65537, x is an integer, and 0<=x<65537, how many values of x are possible?

Answer 1

Fermats little theorem tells us x^65536 = 1 modulo 65537 for all x.
Thus, for x^65535 to also be 1 modulo 65537, we need x^65536 = x^65535 (mod 65537).
Now, thats true for x=0, but x=0 doesn't work in the original. If x is not 0, we can divide both sides by x^65535, since that is coprime with 65537. That tells us that x = 1 (mod 65537), so there is only one possible value for x.

Answer 2

My computer program (written in Java) has carried out the actual calculations and confirmed the conclusions of Stephen and Actuator, namely for x between 1 and 65536, mod(x^65535, 65537) equals 1 only in the case of x=1.

It is interesting to note that the confirmation has taken the computer less than one second to do, obviously Fermet's little theorem is behind the scenes.

Answer 3

The math in stephen m's response sounds very good (and accurate). His final answer may not be entirely clear to you, depending on what level of math you're studying.

He concludes that x = 1 (modulo 65537), but he should have added:

This means that x must be 1.
All other values of x that are equal to 1 (modulo 65537) are greater than 65537, so they do not satisfy the conditions of the problem.