Need proof re prime of the form 8N +/-1

In summary: This theorem follows from the lemma by setting y=0.In summary, the proof by Ramsey follows from the above lemma.
  • #1
ramsey2879
841
3
I need help or direction on how to prove that if A = S^2 - (T^2 + T)/2 Then 8A-1 can not be factored into the form B*C where B and C are coprime and each of the form 8N+/-3. For instance -4*8-1 = -33 can be factored as -3*(8+3) and 5*8-1 = 39 = 3*(8*2-3). Thus neither -4 or 5 can be expressed as S^2 -(T^2+T)/2 where S and T are integers.

So far I have proven that if A = f(S,T) = S^2 - (T^2+T)/2 then A = f(S',T') where S' = 3S + 2T +1 and T' = 4S + 3T + 1, but I don't know where to go from there.

Any ideas.
 
Physics news on Phys.org
  • #2
S^2 = 1, 4, 9, 16, 25 ...
(T^2 +T)/2 = 1, 3, 6, 10, 15, 21...

9-1 = 8; 8*8-1 = 63; 63 = 3*(8*3-3).
therefore your statement is false.
edit: nm, missed the co prime part.
okay; i programmed a check up to many values, as far as i can tell this is true.
how to prove ti is beyond me though.
 
Last edited:
  • #3
phillip1882 said:
S^2 = 1, 4, 9, 16, 25 ...
(T^2 +T)/2 = 1, 3, 6, 10, 15, 21...

9-1 = 8; 8*8-1 = 63; 63 = 3*(8*3-3).
therefore your statement is false.
edit: nm, missed the co prime part.
okay; i programmed a check up to many values, as far as i can tell this is true.
how to prove ti is beyond me though.
Thankyou for your post. Glad to see that someone was interested enough to check my apparent finding.
 
  • #4
Suppose p is prime, 3 or 5 mod 8.
Easy to show that p cannot be expressed as 2*a2-b2.
Also seems to be true that if p|2*a2-b2 then so does p2. That looks like it might be associated with your observation.
 
  • #5
Hi Ramsey, your observation is a consequence of the following:

Lemma: Let N=2x2-y2 with x and y integers. Let p|N be a prime of the form 8k±3. Then ordp(N) is even. (By ordp(N) we mean the exponent of p in the factorization of N.)

Proof: First recall that 2 is a quadratic residue modulo a prime q if and only if q is of the form 8k±1. Since p|N we have 2x2 = y2(mod p). Since 2 is a quadratic nonresidue, it follows that y=x=0 (mod p), and all the terms of the equation N=2x2-y2 can be divided by p2. Repeat as long as N has prime factors of the form 8k±3, and qed.

Your observation follows immediately from this by setting N=8A-1, x=2S, y=2T+1, and by observing that in a coprime factorization N=bc, all factors pa are of the form 8k±1.

I assume the lemma is well known, but I couldn't immediately find a reference. It is analogous to the celebrated theorem about sums of two squares, one version being: A positive integer N can be written as a sum of two squares if and only if for all primes p of the form 4k+3, ordp(N) is even.
 

1. What is the significance of the form 8N +/-1 in prime numbers?

The form 8N +/-1 is significant because it represents a subset of prime numbers, known as Fermat primes. These are prime numbers of the form 2^(2^n) + 1, where n is a non-negative integer. They are named after the mathematician Pierre de Fermat who first studied them.

2. How do you prove that a number of the form 8N +/-1 is prime?

The proof for a number of the form 8N +/-1 being prime is known as the Euler's criterion. It states that if a number a is a Fermat prime, then a^((a-1)/2) is congruent to 1 modulo a. This means that if this condition is satisfied, the number is prime. However, this is only a necessary condition and not sufficient. Further tests and proofs are required to confirm primality.

3. Can you give an example of a prime number of the form 8N +/-1?

One example of a prime number of the form 8N +/-1 is 257, which can be written as 8*32 + 1. This satisfies the form and is also a Fermat prime, as 2^(2^5) + 1 = 2^32 + 1 = 257.

4. How are prime numbers of the form 8N +/-1 used in cryptography?

Fermat primes of the form 8N +/-1 are used in the Diffie-Hellman key exchange algorithm, a popular method for secure communication over unsecured networks. They are also used in the RSA encryption algorithm, which is widely used in digital security and authentication processes.

5. Are there any known methods for generating prime numbers of the form 8N +/-1?

There are various methods for generating prime numbers of the form 8N +/-1, such as the Lucas-Lehmer test and the Proth's theorem. These methods use different techniques and algorithms to efficiently find and verify the primality of numbers in this form. However, there is no known general method for generating all Fermat primes.

Similar threads

Replies
3
Views
2K
Replies
7
Views
782
  • Linear and Abstract Algebra
Replies
3
Views
963
  • Linear and Abstract Algebra
Replies
3
Views
856
  • Linear and Abstract Algebra
Replies
8
Views
663
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
261
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Linear and Abstract Algebra
Replies
7
Views
799
Back
Top