MATH 319 Solutions Assignment 3
27. Show that for all composite n
> 4.
Proof: Since n is composite we know that n = uv with 1 < u,v < n. If u and v are not equal then they each appear as separate terms in (n-1)! and hence n divides (n-1)!. The only difficulty is if u = v. In this case n = u2. u is a term in (n-1)!. Since n > 4 we know that u >2 and hence n = u2 > 2u. Hence 2u is also a term in the product (n-1)!. Hence (n-1)! is divisible by (2u)(u) = 2n and hence by n. Note that this does not work if n = 4.
6. Prove that if p is a prime and , then
of
.
Proof:
is equivalent to
or
By Theorem 1.15 p must
divide one of the two factors.
8. Prove that any number that is a square must have one of 0,1,4,5,6 for its units digit.
Proof. Any n can be written as n = 10k + u where u
is the units digit of n. Let n2
be a square. Then . Thus the units digit of n2
is the units digit of u2. Squaring
0,1,2,…,9 yields units digits of 0,1,4,5,6.
19. Prove that n6 – 1 is divisible by 7 if (n,7) = 1.
Proof: By Fermat’s Theorem if (n,7)
= 1 then since 7 is prime. But
is equivalent to
.
21. Prove that n12 – 1 is divisible by 7 if (n,7) = 1.
Proof: By problem 19 we know that . Squaring both sides of this congruence gives
which is equivalent to
.