Let A be an integer, P an odd prime and n=3 be the smallest integer for which A^n  1 is divisible by P.
Determine the smallest integer m for which (A+1)^m  1 is divisible by P.
In the special case where A=5 and p=31, n=3 is the smallest value of n such that 5^n  1 is divisible by 31. And 6 is the smallest value of m for which 6^m  1 is divisible by 31. So m must be at least 6. To show that m=6 always works in general, consider that A^3  1=pk > (A1)(A^2+A+1)=pk but since p does not divide A1, p divides the other factor. So let pj=A^2+A+1. Now (A+1)^6  1=(A^2+2A+1)^3  1=(pj+A)^3  1. But all terms of this last expression have a factor of p except A^3  1 which itself equals pk so (A+1)^6  1 is divisible by p.

Posted by Dennis
on 20070108 15:19:42 