 mersenneforum.org > Math Proving, for A > 1, (A+1)^n mod A = 0
 Register FAQ Search Today's Posts Mark Forums Read 2017-12-20, 14:52 #1 MushNine   Nov 2017 United Kingdom 13 Posts Proving, for A > 1, (A+1)^n mod A = 0   2017-12-20, 15:14 #2 CRGreathouse   Aug 2006 22·5·293 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?    2017-12-20, 23:51 #3 henryzz Just call me Henry   "David" Sep 2007 Cambridge (GMT) 32×17×37 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.   2017-12-21, 10:27 #4 MushNine   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^948234-1 is prime, just tell them that it's divisible by 306. Probably. NB: 4^1-1 or 8^1-1 are prime. They're divisible by 3 or 7 respectively. It only works being non-prime if the value is squared, cubed etc. (4^2-1 is 15 and is divisible by 3) Last fiddled with by MushNine on 2017-12-21 at 10:35   2017-12-21, 11:18   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by MushNine (inductive step? I don't really understand induction :P)
https://en.wikipedia.org/wiki/Mathematical_proof   2017-12-21, 12:03   #6
Nick

Dec 2012
The Netherlands

22·73 Posts Quote:
 Originally Posted by MushNine (Proving, for A > 0, (A+1)^n -1 = Am) (m is just some number which satisfies the equation)
Let $$a$$ and $$b$$ be any numbers.
1. What is $$(a-b)(a+b)$$?
2. What is $$(a-b)(a^2+ab+b^2)$$?
3. What is $$(a-b)(a^3+a^2b+ab^2+b^3)$$?
4. What is $$(a-b)(a^4+a^3b+a^2b^2+ab^3+b^4)$$?
Can you see the pattern?
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.   2017-12-22, 07:54 #7 LaurV Romulan Interpreter   Jun 2011 Thailand 8,543 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 2017-12-22 at 07:55   2017-12-22, 18:13   #8
MushNine

Nov 2017
United Kingdom

158 Posts Quote:
 Originally Posted by LaurV 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)
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.   2018-01-03, 23:26 #9 JeppeSN   "Jeppe" Jan 2016 Denmark 109 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)^n-1$$ can never be prime because it is divisible by $$A$$. Therefore we can consider instead $\frac{(A+1)^n-1}{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 2018-01-03 at 23:27   2018-01-04, 03:29 #10 LaurV Romulan Interpreter   Jun 2011 Thailand 8,543 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^15-1)/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 2018-01-04 at 03:30  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post jasonp FactorDB 3 2011-10-17 18:04 Rodrigo Information & Answers 28 2011-02-14 23:43 CRGreathouse Software 13 2011-01-30 14:30 AntonVrba Math 2 2008-10-06 00:53 eepiccolo Lounge 10 2003-02-03 05:15

All times are UTC. The time now is 09:49.

Wed Jun 3 09:49:02 UTC 2020 up 70 days, 7:22, 2 users, load averages: 1.28, 1.35, 1.49