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

[MushNine]

[CRGreathouse]

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

[henryzz]

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]

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]

Originally Posted by MushNine

(inductive step? I don't really understand induction :P)

https://en.wikipedia.org/wiki/Mathematical_proof

[Nick]

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.

[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)

[MushNine]

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.

[JeppeSN]

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]

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.