mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2017-12-20, 14:52   #1
MushNine
 
MushNine's Avatar
 
Nov 2017
United Kingdom

158 Posts
Post Proving, for A > 1, (A+1)^n mod A = 0

MushNine is offline   Reply With Quote
Old 2017-12-20, 15:14   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

592310 Posts
Default

I think you've made a mistake in transcribing the problem in the title. Maybe that's why you're having trouble solving it?
CRGreathouse is offline   Reply With Quote
Old 2017-12-20, 23:51   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131328 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2017-12-21, 10:27   #4
MushNine
 
MushNine's Avatar
 
Nov 2017
United Kingdom

D16 Posts
Post 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
MushNine is offline   Reply With Quote
Old 2017-12-21, 11:18   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by MushNine View Post
(inductive step? I don't really understand induction :P)
https://en.wikipedia.org/wiki/Mathematical_proof
science_man_88 is offline   Reply With Quote
Old 2017-12-21, 12:03   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

22·359 Posts
Default

Quote:
Originally Posted by MushNine View Post
(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.
Nick is offline   Reply With Quote
Old 2017-12-22, 07:54   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

32·971 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2017-12-22, 18:13   #8
MushNine
 
MushNine's Avatar
 
Nov 2017
United Kingdom

D16 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
MushNine is offline   Reply With Quote
Old 2018-01-03, 23:26   #9
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

9B16 Posts
Thumbs up

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
JeppeSN is offline   Reply With Quote
Old 2018-01-04, 03:29   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

32×971 Posts
Default

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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality proving of DB factors? jasonp FactorDB 3 2011-10-17 18:04
'Verifying' a Mersenne prime vs. 'proving' it Rodrigo Information & Answers 28 2011-02-14 23:43
Primality proving CRGreathouse Software 13 2011-01-30 14:30
New Class of primes - proving algorithm AntonVrba Math 2 2008-10-06 00:53
Countdown to proving M(6972593) is #38 down to less than 10! eepiccolo Lounge 10 2003-02-03 05:15

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

Wed Sep 23 23:49:56 UTC 2020 up 13 days, 21 hrs, 0 users, load averages: 1.98, 1.79, 1.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.