mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   Proving, for A > 1, (A+1)^n mod A = 0 (https://www.mersenneforum.org/showthread.php?t=22807)

 MushNine 2017-12-20 14:52

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

[$][/$]

 CRGreathouse 2017-12-20 15:14

I think you've made a mistake in transcribing the problem in the title. Maybe that's why you're having trouble solving it? :smile:

 henryzz 2017-12-20 23:51

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.

 MushNine 2017-12-21 10:27

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)

 science_man_88 2017-12-21 11:18

[QUOTE=MushNine;474488]
(inductive step? I don't really understand induction :P)[/QUOTE]
[url]https://en.wikipedia.org/wiki/Mathematical_proof[/url]

 Nick 2017-12-21 12:03

[QUOTE=MushNine;474488](Proving, for A > 0, (A+1)^n -1 = Am)
(m is just some number which satisfies the equation)
[/QUOTE]
Let $$a$$ and $$b$$ be any numbers.
[LIST=1][*]What is $$(a-b)(a+b)$$?[*]What is $$(a-b)(a^2+ab+b^2)$$?[*]What is $$(a-b)(a^3+a^2b+ab^2+b^3)$$?[*]What is $$(a-b)(a^4+a^3b+a^2b^2+ab^3+b^4)$$?[/LIST]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.

 LaurV 2017-12-22 07:54

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)

 MushNine 2017-12-22 18:13

[QUOTE=LaurV;474572]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)[/QUOTE]

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.

 JeppeSN 2018-01-03 23:26

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

 LaurV 2018-01-04 03:29

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.

 All times are UTC. The time now is 07:30.