Divisibility ProofDate: 10/26/1999 at 21:30:20 From: Pat Subject: Divisibility Properties Prove that: 1. n^5 - n is divisible by 30 2. n^7 - n is divisible by 42 Using induction is not permitted. Only use divisibility to prove them. I'm not sure whether I need to use modulo or something else. Date: 10/26/1999 at 22:05:22 From: Doctor Rob Subject: Re: Divisibility Properties Thanks for writing to Ask Dr. Math, Pat. Factor these as follows: n^5 - n = n*(n-1)*(n+1)*(n^2+1) n^7 - n = n*(n-1)*(n+1)*(n^2+n+1)*(n^2-n+1) Now n*(n-1)*(n-2) is always divisible by 6. There remains to show divisibility by 5 and 7. Fermat's Little Theorem takes care of that: If prime p does not divide a, then a^(p-1) = 1 (mod p). This implies that n^p - n = 0 (mod p), for every n and every prime number p. Now use that with p = 5 and with p = 7. If you can't use that theorem, then you can observe that if n = 0, 1, or 4 (mod 5) then 5 | n*(n-1)*(n+1). 5 | n^2 + 1 iff 5 | n^2 + 1 + 5*(1-n) = n^2 - 5*n + 6 = (n-2)*(n-3) iff n = 2 or 3 (mod 5). Thus no matter what n is congruent to modulo 5, 5 divides n^5 - n. Similarly, if n = 0, 1, or 6 (mod 7) then 7 | n*(n-1)*(n+1). 7 | n^2 + n + 1 iff 7 | n^2 - 6*n + 8 = (n-2)*(n-4) iff n = 2 or 4 (mod 7). 7 | n^2 - n + 1 iff 7 | n^2 - 8*n + 15 = (n-3)*(n-5) iff n = 3 or 5 (mod 7). Thus no matter what n is congruent to modulo 7, 7 divides n^7 - n. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/