# Number theory prime divisibility problem

• Dec 17th 2013, 07:42 PM
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.
• Dec 17th 2013, 07:50 PM
SlipEternal
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?
• Dec 18th 2013, 05:57 AM
Re: Number theory prime divisibility problem
Quote:

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).
• Dec 18th 2013, 07:23 AM
Re: Number theory prime divisibility problem
Quote:

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..
• Dec 18th 2013, 08:58 AM
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.
^embarrassingly i have found yet another hole in my above argument in post #5. :( even $n$ can very well be a solution