Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By SlipEternal

Math Help - Number theory prime divisibility problem

  1. #1
    Newbie
    Joined
    Jul 2013
    From
    New Delhi
    Posts
    10

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,880
    Thanks
    742

    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?
    Thanks from Diadem
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2013
    From
    New Delhi
    Posts
    10

    Re: Number theory prime divisibility problem

    Quote Originally Posted by SlipEternal View Post
    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).
    Last edited by Diadem; December 18th 2013 at 06:32 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2013
    From
    New Delhi
    Posts
    10

    Re: Number theory prime divisibility problem

    Quote Originally Posted by SlipEternal View Post
    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..
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2013
    From
    New Delhi
    Posts
    10

    Re: Number theory prime divisibility problem

    Quote Originally Posted by SlipEternal View Post
    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.
    Last edited by Diadem; December 18th 2013 at 09:08 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2013
    From
    New Delhi
    Posts
    10

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 27th 2010, 12:45 PM
  2. Some Prime Number Divisibility Questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 08:17 PM
  3. Number theory, prime numbers, interesting problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 21st 2007, 01:23 AM
  4. Number Theory: Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2007, 06:56 PM
  5. Number theory, divisibility by 22
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 12th 2006, 04:30 PM

Search Tags


/mathhelpforum @mathhelpforum