All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Divisibility (Posted on 2007-01-08) Difficulty: 3 of 5
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.

No Solution Yet Submitted by atheron    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
some thoughts | Comment 1 of 6
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 --> (A-1)(A^2+A+1)=pk but since p does not divide A-1, 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 2007-01-08 15:19:42
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information