Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Twin Primes of the form (8n+5,8n+7)

  1. Jun 7, 2006 #1
    Conjecture If [tex]8n+5[/tex] and [tex]8n+7[/tex] are twin primes then their product divides [tex]S_{4n+3}[/tex] where
    [tex]S_{n} = 6S_{n-1} - S_{n-2} \mid S_{0} = 0 [/tex]

    Prove or disprove
     
  2. jcsd
  3. Jun 8, 2006 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I don't see any way to do this until you actually DEFINE "Sn". Since your recurssion for Sn involves both Sn-1 and Sn-2, just saying "S0= 0" is not enough. What is S1?
     
  4. Jun 8, 2006 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The standard guess, given it's ramsey, would be that S_n is the n'th square triangular number. That would make S_1=1, however, in that case S_2 would be 6, which is only one of square and triangular, so I am mystified.
     
  5. Jun 8, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Note if S_1=1, then (S_2)^2=6^2=36, the 3rd square triangular number, and so on.

    It looks true. If we set u=1+sqrt(2), v=sqrt(2)-1 then S_n=(u^(2n)-v^(2n))/sqrt(8). It's enough to show that if p=8n+5 or 7 is prime then p divides u^(8n+6)-v^(8n+6), which will follow if you can show p divides u^(16n+12)-1.

    If p=8n+5, then 2^((p-1)/2)=-1 mod p as 2 is not a quadratic residue mod p. Thus u^p=1-sqrt(2) mod p and u^16n+12-1=u^(2p+2)-1=(1-sqrt(2))^2*u^2-1=0 mod p. Similar for p=8n+7, except 2 is a quadratic residue in this case.

    Notice this has nothing to do with them being twin primes. This is almost the same as the proof of the Lucas-Lehmer test. I think the reverse implication might be true as well, if 8n+5 divides S_(4n+3) then 8n+5 is prime (same for 7), but I haven't worked out the details.
     
  6. Jun 8, 2006 #5
    S_1 is any integer I didn't think one would consider letting it be otherwise.
     
  7. Jun 8, 2006 #6
    Yes it works for all primes. It is interesting because if 2 is a square modulus n then S_((n-1)/2) = 0 modulus n otherwise S_((n+1)/2) = 0 mod n. For twin primes thes are the same numbers. The converse is not true. One example is n = 19*59 also works.
     
  8. Jun 8, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Changing S_1 from 1 to any integer won't affect post #4 as this will just multiply all the S_n's by your new S_1.

    Maybe I mucked something up, but 2 isn't a residue mod 19*59 but I get S_((19*59+1)/2) =S_1 mod 19*59. However S_((19*59-1)/2) is 0 mod 19*59? In any case, the converse does appear false, n=29*41=1189, 2 is not a quadratic residue and S_1190= 0 mod 1189.
     
  9. Jun 11, 2006 #8
    I don't understand your proof here. The divisor for S_n is 4sqrt(2). Also, I get u^p = u mod p by Fermat's little theorm.
    Thus u^(16n+10) = (u^p)*(u^p) = u*u = 3+2sqrt(2) where p =8n+5
    and u^(16n+11) = 7+5sqrt(2)
    and u^(16n+12) -1 =16+12sqrt(2)

    how is 16 + 12sqrt(2) divisible by p?

    My attempted proof:
    p|S_(4n-3) <--> p|(u^(8n+6)-v^(8n+6))/4sqrt(2)
    --> p|(u^2-v^2)/4sqrt(2) (Fermats little therom)
    --> p|(3 +2sqrt(2) - (3-2sqrt(2)))/4sqrt)
    --> p|1

    where did I go wrong?
     
    Last edited: Jun 11, 2006
  10. Jun 11, 2006 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    That's correct, I have a typo. No change in the proof though, p is odd so you can remove as many multiples of 2 as you like.

    u is not an integer, Fermat's doesn't apply directly. Use the binomial theorem to expand, p divides each coefficient except the first and last, use the fact 2 is not a quadratic residue.
     
    Last edited: Jun 11, 2006
  11. Jun 11, 2006 #10
    continuing
    --> p|(1+2^(4n+3) -(1 + 2^(4n+3)) +pM) /4sqrt(2)
    --> p|0
     
  12. Jun 11, 2006 #11

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Where does this come from? What's the point of M? It looks like you're trying to do something like (a+b)^(p+1)=a^(p+1)+b^(p+1) mod p, which is just not true.
     
  13. Jun 11, 2006 #12
    It depends upon what rule you used in the test for p being a prime. 19*59 is of the form 8n+1 which if prime would include 2 as a residue and you would subtract 1 from 19*59 before dividing by 2 to get S_(10*56) = 0 mod 19*59 correctly which to me would falsely indicate that 19*59 is prime. You also stated the rule in this fashion when you said "I think the reverse implication might be true as well, if 8n+5 divides S_(4n+3) then 8n+5 is prime (same for 7), but I haven't worked out the details." 1189 is of the form 8n+5, if this is a prime then 2 would not be a residue and you add 1 correctly to get S_(595) = 0 mod 29*41 which would also falsely indicate that 29*41 is prime. I only later stated the rule as subtracting 1 if 2 is a residue and adding 1 if 2 is not a residue when in fact I merely used the value modulus 8 to determine whether to add or subtract 1 as you earlier indicated the proposed test to be.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Twin Primes of the form (8n+5,8n+7)
  1. Twin Primes (Replies: 3)

  2. 5 and 7 (Replies: 6)

Loading...