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

New property of primes

  1. Aug 30, 2012 #1
    I would like to show that if a prime number P mod 8 is a) 1 or 7 or b) 3 or 5 then

    a) [tex]\frac{(P+1)}{2}(1-sqrt{2})(3+sqrt{8})^\frac{P-1}{2}+ \frac{(P+1)}{2}(1+sqrt{2})(3-sqrt{8})^\frac{P-1}{2} = (\frac{P-3}{2} + 2)[/tex] mod P

    b) [tex]\frac{(P+1)}{2}(1-sqrt{2})(3+sqrt{8})^\frac{P-1}{2}+ \frac{(P+1)}{2}(1+sqrt{2})(3-sqrt{8})^\frac{P-1}{2} = (\frac{P-3}{2} - 2)[/tex] mod P

    Any suggestions
    Last edited: Aug 30, 2012
  2. jcsd
  3. Aug 31, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    in (a), doesn't the RHS reduce to (P+1)/2, allowing that to be cancelled as a factor throughout?
    This doesn't apply to (b), so there's a curious asymmetry.
  4. Aug 31, 2012 #3


    User Avatar
    Gold Member

    [itex]a^{p-1} - 1 \equiv0 mod(p)[/itex] the factorization is: [itex](a^{\stackrel{p-1}{2}} - 1)(a^{\stackrel{p-1}{2}} + 1)[/itex]
  5. Aug 31, 2012 #4
    That is correct. The formula on the left hand side is the direct formula for S_((P-1)/2) where S_(0) = (P+1)/2; S_(1) = - S_(0) and S_(n) = 6S_(n-1) - S_(n-2). In a) the factor (P+1)/2 does cancel out but I left it in to show the relationship to b). There is a curious asymmetry for most all recursive series of the form S_n = 6S_(n-1) - S_(n-2) mod P depending upon whether P is a prime of the form 8n +/- 1 or 8n +/-3, but I agree that the one here is quite curious.
    Last edited: Aug 31, 2012
  6. Aug 31, 2012 #5
    Although that is true for integer a, I don't see that it applies to (3 +/- sqrt8)^(P-1)/2
  7. Sep 2, 2012 #6


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Isn't there a factor of 2 missing somewhere in (a)? After cancelling the (P+1)/2, the LHS always produces an even number. But it does appear to be always 2 when P congruent to 1 or 7 (8).
  8. Sep 2, 2012 #7

    What you have in (a), after a little algebra, is
    $$\frac{p+1}{2}\left(1-\sqrt 2\right)\left(3+\sqrt 8\right)^{(p-1)/2}+\frac{p+1}{2}\left(1+\sqrt 2\right)\left(3-\sqrt 8\right)^{(p-1)/2}=\frac{p+1}{2}\Longleftrightarrow (1-\sqrt 2 )(3+2\sqrt 2)^{(p-1)/2}+(1+\sqrt 2)(3-2\sqrt 2)^{(p-1)/2}=1$$

    But, for example for [itex]\,p=7\,[/itex] , we get:
    $$(3\pm2\sqrt 2)^3=27\pm 54\sqrt 2+72\pm 16\sqrt 2\Longrightarrow \begin{align*} (1-\sqrt 2)(3+2\sqrt 2)^3=&-41-29\sqrt 2\\(1+\sqrt 2)(3-2\sqrt 2)^3=&-41+29\sqrt 2\end{align*}$$

    If we add the above we get [itex]\,-82\neq 1\,[/itex] , so either I'm making a mistake, or I didn't understand correctly...or the formula's wrong.

  9. Sep 2, 2012 #8


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    As I pointed out in post #6, there seems to be a factor of 2 error.
    If you halve the LHS you get -41, which is 1 mod 7 as required.
  10. Sep 3, 2012 #9
    Your right. There is a factor of 2 error in both a) and b). As I said in a later post. This is a direct formula for S_(n) where S_(0) = (P+1)/2 and S_(1) = - S_(0). I am sorry for the error. If you substitute (P+1)/4 for (P+1)/2 you get correct results for S_(0), S_(1) and

    Thankyou haruspex and DonAntonio for pointing out my error so it could be corrected.
  11. Sep 6, 2012 #10


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Fwiw, I investigated the behaviour of sk+1 = 2 sk + sk-1 mod p, s0=s1=1, looking for where it hits 1. I see the same dependency on p mod 8:
    - for 1 or 7 mod 8, it repeats every p-1 terms
    - for 3 or 5 mod 8, it repeats every 2p+2 terms
    There are relatively few where it repeats more often as well. It repeats X times as often as follows:
    p X
    29 3
    41 4
    59 3
    79 3
    103 3
    137 2
    179 5
    197 11
    199 11
    Strange sequence. Also looked at modulo odd composites up to 91. No obvious patterns. The only one that behaved like a prime (i.e. as above) was 35.
  12. Sep 6, 2012 #11
    This sequence can be broken up into two intermeshed sequences of the form Sk+1 = 6*Sk - Sk-1. Is it correct that you were aware of this? PS see OEIS sequences A182431, A182439 through A182441 which I posted. The relation to the the sequences here where S0 = N and S1=-N (same for your sequence type and my sequence type) is explained in the comments and in the sequences referenced there.
    Last edited: Sep 6, 2012
  13. Sep 9, 2012 #12
    I also have found that the following identity holds and it does not depend on the value of P mod 8:

    [tex]\frac{(P+1)}{2}(1-sqrt{2})(3+sqrt{8})^\frac{P+1}{2}+ \frac{(P+1)}{2}(1+sqrt{2})(3-sqrt{8})^\frac{P+1}{2} = -1 [/tex] mod P

    It appears to hold for all primes and certain composites such as 169.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook