20171220, 14:52  #1 
Nov 2017
United Kingdom
13 Posts 
Proving, for A > 1, (A+1)^n mod A = 0

20171220, 15:14  #2 
Aug 2006
3^{2}·5·7·19 Posts 
I think you've made a mistake in transcribing the problem in the title. Maybe that's why you're having trouble solving it?

20171220, 23:51  #3 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5853_{10} Posts 
As it stands I believe it to be false. For n >= 0, it is fairly easy to show that (A+1)^n = 1 mod A.

20171221, 10:27  #4 
Nov 2017
United Kingdom
13 Posts 
RE: CRGreatHouse
I stupidly pressed enter while writing the title. I meant to put a minus one before the mod part!
As a result, there was no content in my post! Anyway, I might as well prove it :P (Proving, for A > 0, (A+1)^n 1 = Am) (m is just some number which satisfies the equation) (base case for induction) n=1: (A+1)^1 1 = Am (A+1)1 = A = Am (m=1) ALSO (A+1) = Am+1 (hypothesis) n=k: (A+1)^k 1 = Am ALSO (A+1)^k = Am+1 (inductive step? I don't really understand induction :P) n=k+1: (A+1)^k+1 1 = Am ((A+1)^k)*((A+1)^1) 1 = Am (Am_1+1)(Am_2+1) 1 = Am A^2*m_1*m_2+Am_1+Am_2+1 1 = Am A^2*m_1*m_2+Am_1+Am_2 = Am (m=A*m_1*m_2+m_1+m_2) I think that proves it! So if someone says 307^9482341 is prime, just tell them that it's divisible by 306. Probably. NB: 4^11 or 8^11 are prime. They're divisible by 3 or 7 respectively. It only works being nonprime if the value is squared, cubed etc. (4^21 is 15 and is divisible by 3) Last fiddled with by MushNine on 20171221 at 10:35 
20171221, 11:18  #5 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 

20171221, 12:03  #6  
Dec 2012
The Netherlands
13·127 Posts 
Quote:
If you take any integer \(A\) and set \(a=A+1\) and \(b=1\) in the above, it gives your result. So this is a more general version. 

20171222, 07:54  #7 
Romulan Interpreter
Jun 2011
Thailand
3^{3}·347 Posts 
Even simpler, A+1 = 1 (mod A).
Therefore, (A+1)^n = 1^n = 1 (mod A). Nothing to prove. (to be moved to misc math) Last fiddled with by LaurV on 20171222 at 07:55 
20171222, 18:13  #8 
Nov 2017
United Kingdom
13 Posts 
Fair enough. I just couldn't find a proof anywhere and thought I might just make sure it's true  at the very least. So I'm glad I achieved a goal of some sort.

20180103, 23:26  #9 
"Jeppe"
Jan 2016
Denmark
2·83 Posts 
This is related to one way you can generalize Mersenne primes \(2^n  1\).
If you try to change the \(2\) into \(A+1\) with \(A>1\), we have seen above that the resulting \((A+1)^n1\) can never be prime because it is divisible by \(A\). Therefore we can consider instead \[\frac{(A+1)^n1}{A}\] which may or may not be prime, just like Mersenne numbers. This is what some people call repunits in base \(A+1\). For example \(\frac{10^{19}1}{9}\) or 1111111111111111111 is prime. /JeppeSN Last fiddled with by JeppeSN on 20180103 at 23:27 
20180104, 03:29  #10 
Romulan Interpreter
Jun 2011
Thailand
3^{3}·347 Posts 
Yet, this is still a divisibility sequence, the terms can be prime only if the number of 1 in the sequence is prime, that is, only if the n is prime. The proof is very simple, and similar to the "binary proof" for mersenne numbers: if the number of 1 in the sequence is not prime, then split them in equal strings and you just factored your number. For example, N=(10^151)/9=111 111 111 111 111=111*(1001001001001)=11111 11111 11111=11111*(10000100001), and you have already (at least) two different ways to factor N, without any calculus.
So, for such a number to be prime, n must be prime. Last fiddled with by LaurV on 20180104 at 03:30 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primality proving of DB factors?  jasonp  FactorDB  3  20111017 18:04 
'Verifying' a Mersenne prime vs. 'proving' it  Rodrigo  Information & Answers  28  20110214 23:43 
Primality proving  CRGreathouse  Software  13  20110130 14:30 
New Class of primes  proving algorithm  AntonVrba  Math  2  20081006 00:53 
Countdown to proving M(6972593) is #38 down to less than 10!  eepiccolo  Lounge  10  20030203 05:15 