SOLUTION: An integer n is called square-free if there does not exist a prime number p such that {{{p^2}}} divides n. a) Let {{{n>=2}}} be an integer with the property that {{{a^n=a (mod n)

Algebra ->  Divisibility and Prime Numbers -> SOLUTION: An integer n is called square-free if there does not exist a prime number p such that {{{p^2}}} divides n. a) Let {{{n>=2}}} be an integer with the property that {{{a^n=a (mod n)      Log On


   

Question 1019197: An integer n is called square-free if there does not exist a prime number p such that p%5E2 divides n.
a) Let n%3E=2 be an integer with the property that a%5En=a++%28mod+n%29 for every integer a. Prove that n is square-free.
b) Give an example of a square-free integer n%3C=30 such that a%5En != a (mod n) for some integer a.
Answer by richard1234(7193) About Me  (Show Source):
You can put this solution on YOUR website!
a) Suppose n is divisible by for some prime p. Because the statement must hold for every integer a, it must hold when a = p. However the congruence cannot possibly hold because is divisible by , and if the congruence holds mod n, it must hold mod . So we have a contradiction, so n is square-free.

b) If n is prime, then the congruence always holds by Fermat's little theorem. So we should pick a composite number, say n = 4. The congruence fails to hold true when a = 2, since .