Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A quick primality test says: if for some coprime to , then is composite. The number fools it. Factor into primes. Then prove that for every coprime to , by applying Fermat's theorem to each prime factor and noting how relates to . Give the smallest and the largest prime factor and the remainder of on division by .
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. and an integer with .
Step 1. Factor. The digit sum is , so : .
Step 2. The exponent. . So is a multiple of , and , which are for .
Step 3. Fermat for each prime. Since is coprime to , no prime factor divides . So , and . Raising to the powers , and gives modulo each prime.
Step 4. Combine. The three primes are distinct, so their product divides : . Proof complete.
Step 5. The case . , so , remainder .
Answer: smallest prime factor , largest , and leaves remainder .
What if? A number like this, square-free with for every prime factor , is a Carmichael number. This test is called Korselt's criterion.
Log in to join the discussion.
Loading…