Proving, for A > 1, (A+1)^n mod A = 0
[$][/$]

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:

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.

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) 
[QUOTE=MushNine;474488]
(inductive step? I don't really understand induction :P)[/QUOTE] [url]https://en.wikipedia.org/wiki/Mathematical_proof[/url] 
[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 \((ab)(a+b)\)?[*]What is \((ab)(a^2+ab+b^2)\)?[*]What is \((ab)(a^3+a^2b+ab^2+b^3)\)?[*]What is \((ab)(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. 
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=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. 
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 
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. 
All times are UTC. The time now is 07:30. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.