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)

Question 1019197: An integer n is called square-free if there does not exist a prime number p such that divides n.
a) Let be an integer with the property that for every integer a. Prove that n is square-free.
b) Give an example of a square-free integer such that != a (mod n) for some integer a.
Answer by richard1234(7193) (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

.
RELATED QUESTIONS
(a) Let p be a prime number greater than 3. What are the possible remainders of p upon... (answered by jim_thompson5910)

For arbitrary positive integers k, m, and n, will there exist a prime p such that... (answered by Edwin McCravy)

Let p(n) and s(n) denote the product and the sum, respectively, of the digits of the... (answered by Edwin McCravy)

Let n be a positive integer, k the number of prime numbers less than or equal to n, and... (answered by richard1234)

if n is an integer greater then 1, such that n divided by 4 yields a remainder of 0,... (answered by tommyt3rd)

Prove that there exists some integer n such that n^2 + 123457 is a perfect... (answered by Edwin McCravy)

let k be an integer and p is a prime such that the quadratic equation x^2+kx+p=0 has two... (answered by ankor@dixie-net.com)

Dealing with contradiction: Show that for any positive integer a and any prime p, if p... (answered by venugopalramana)

Let $P(x)$ be a nonconstant polynomial, where all the coefficients are nonnegative... (answered by jim_thompson5910)