Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Prove that is a multiple of for every integer . Use the first form of Fermat's theorem, , for each of the primes , and . For and you must first lift or to the seventh power. Then show that is the largest integer with this property. Give that integer and the value of at .
For a prime with , Fermat's little theorem gives , so exponents can be reduced modulo :
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Given. .
Step 1. Modulo 7. Fermat's first form gives at once.
Step 2. Modulo 3. Fermat gives . Then .
Step 3. Modulo 2. , so every power for . In particular .
Step 4. Combine. , and all divide and are coprime, so .
Step 5. Best possible. and . Here , so any integer dividing every divides .
Answer: is the largest integer that always divides , and . Proof complete.
What if? The same reasoning shows is always a multiple of : these are the primes with dividing .
Log in to join the discussion.
Loading…