# Thread: Number theory prime divisibility problem

1. ## Number theory prime divisibility problem

Hello, as part of a proof I am working on, I need to find all $p$ s.t. $p| 3^n + 5^n$ and $p | n^2 -1$. $n\in\mathbb{Z^{+}}$ and $p$ is prime. This part of my proof has stumped me and I have had no success in attacking this part and I am not sure as to whether I am just going down a blind alley here and there is more efficient way. Any help/ ideas/ hints would be much appreciated.

2. ## Re: Number theory prime divisibility problem

Finding all such $p$ is not a proof. Proving that the set of all such $p$ you find is a proof. What do you have so far?

3. ## Re: Number theory prime divisibility problem

Originally Posted by SlipEternal
Finding all such $p$ is not a proof. Proving that the set of all such $p$ you find is a proof. What do you have so far?
Thank you for taking the time to reply.

My apologies as it was poor wording in the post 1. This is not the question itself that I am working on but is the route I have taken down towards my solution of another question. Essentially, I am trying to prove that $\gcd{(3^n + 5^n , n^2 - 1)} = 8, \ n \in \mathbb{Z^{+}}$ (or what I was trying to convey in the first post was that I was ultimately trying to show the only such $p$ that exists is 2 - I do not know this to be true or not, I have only conjectured) and I haven't been able to make any progress in this part of the solution so I was inquiring whether this is even true to begin with (i.e. if anyone could think of a counterexample) and even if it is true, is the proof of it tangible (and if anyone could give me a hint as to how to start to prove this).

4. ## Re: Number theory prime divisibility problem

Originally Posted by SlipEternal
Finding all such $p$ is not a proof. Proving that the set of all such $p$ you find is a proof. What do you have so far?
Actually, nevermind, the conjecture is incorrect, I have found a counterexample. Back to the drawing board, I suppose..

5. ## Re: Number theory prime divisibility problem

Originally Posted by SlipEternal
Finding all such $p$ is not a proof. Proving that the set of all such $p$ you find is a proof. What do you have so far?
Apologies to bother you again but I am stuck. The problem (which I was trying to find a solution for) is to find all positive integers $n$ s.t. $\dfrac{3^n + 5^n}{n^2 -1} \in \mathbb{Z^{+}}$. My initial attempt was that I showed solutions can only exist for odd $n$ and then showed that $3^n + 5^n \equiv n^2 - 1 \equiv 0 \pmod{8}$ for all odd $n\geq 3$. I conjectured that the only solution is for $n=3$ (dunno if the conjecture is correct but $n=3$ is a solution) and tried to prove this by what I set out in the OP - I wished to show that the only prime which divides both is 2 and I would be done (as $3^n + 5^n \equiv 8 \sum_{i=0}^{n-1} 5^i (-3)^{n-1-i} \wedge \sum_{i=0}^{n-1} 5^i (-3)^{n-1-i} \equiv 1\not\equiv 0 \pmod{2}$ for odd $n$) but 2 is not the only such prime and now I do not know how to proceed. Am I along the right lines for a solution or is there a better method? Thank you.

6. ## Re: Number theory prime divisibility problem

^embarrassingly i have found yet another hole in my above argument in post #5. even $n$ can very well be a solution