My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree7Thanks
Reply
 
LinkBack Thread Tools Display Modes
June 17th, 2018, 01:44 PM   #31
Newbie
 
Joined: Mar 2018
From: United States

Posts: 23
Thanks: 0

Quote:
Originally Posted by penrose View Post
If $p$ is a prime and $2p+1$ is a prime, then $2p+1$ divides $2^p-1$ or $2^p+1$
Quote:
Originally Posted by cjem View Post
If you work a little harder, you can say when each case happens:
Does the proof below make sense?
.
The following identities are mod ($2p+1$):
.
Case 1:
If $2p+1$ divides $2^p-1$,
.
$2^p ≡ 1$
.
$2^{p-1}$ ≡ $p+1$
.
$(2^{(p-1)/2})^2$ ≡ $p+1$
.
Since a mod 4 square can only be 0 or 1, the only available solution is $p$ mod $4$ ≡ $3$. Example: $p$ = 11
.
Case 2:
If $2p+1$ divides $2^p+1$,
.
$2^p$ ≡ $2p$
.
$2^{p-1}$ ≡ $p$
.
$(2^{(p-1)/2})^2$ ≡ $p$
.
Since a mod 4 square can only be 0 or 1, the only available solution is $p$ mod $4$ ≡ $1$ Example: $p$ = 5
penrose is offline  
 
June 18th, 2018, 01:17 AM   #32
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 219
Thanks: 70

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
Originally Posted by penrose View Post
X
To deduce the final statement in the first case, you would need to know that $(2^{(p-1)/2})^2$ ≡ $p+1 \bmod 4$. But all you've shown is $(2^{(p-1)/2})^2$ ≡ $p+1 \bmod {2p+1}$. There's a similar issue in the second case.
cjem is offline  
July 18th, 2018, 04:45 AM   #33
Newbie
 
Joined: Mar 2018
From: United States

Posts: 23
Thanks: 0

Quote:
Originally Posted by penrose View Post
Given any n, if $2n+1$ is a prime, then $2n+1$ divides $2^n-1$ or $2^n+1$
For a proof of this, let's introduce some terminology to keep track of what is going on.

For a given odd $n$, let the cycle generated by $2$, {$2^i$ mod $n$}, be represented by $< n >_2$. For example, $< 9 >_2$ = {$2, 4, 8, 7, 5, 1$}. We can call this the Mersenne Cycle or Mersenne Group for $n$. We can call the size or length of this group the Mersenne Order or Mersenne Length and designate it by $[n]_2$. Then $[9]_2$ = $6$.

The Mersenne Group is a subgroup (not necessarily proper) of the full multiplicative group mod $n$, so its length must divide the size of the full group. In the case of $9$, they are the same. In the case of $7$, $< 7 >_2$ = {$2, 4, 1$} and $[7]_2$ = $3$. The full multiplicative group mod $7$ = {$1, 2, 3, 4, 5, 6$} and has size $6$. We see that $3$ divides $6$. The full multiplicative group mod $n$ has size $n-1$ if and only if $n$ is a prime number.

In any case, $n$ is a divisor of the Mersenne Number $2^{[n]_2}$ - $1$, which is the smallest Mersenne Number that $n$ divides. For example, $9$ is a divisor of $2^6 - 1$.

This is where I will stop for now, to not make this post too long.
penrose is offline  
July 19th, 2018, 05:03 PM   #34
Newbie
 
Joined: Mar 2018
From: United States

Posts: 23
Thanks: 0

Quote:
Originally Posted by penrose View Post
Given any n, if $2n+1$ is a prime, then $2n+1$ divides $2^n-1$ or $2^n+1$
Continuing with the preceeding post, if $2n+1$ is a prime, then the full multiplicative group mod $2n+1$ consists of the elements {$1, 2, 3, . . .2n$} and has size $2n$. Let $m = [2n + 1]_2$. Then $2n + 1$ is a divisor of $2^m-1$ and $m$ is a divisor of $2n$.

Finally, we need to know that if $r$ is a divisor of $s$, then $2^r - 1$ divides $2^s-1$. This can be seen from

$2^s - 1$ = ($2^r - 1$)($2^{s - r} + 2^{s - 2r} + . . . + 2^r + 1$)

So $2n + 1$ divides $2^m - 1$ which divides $2^{2n} - 1$ = ($2^n - 1$)($2^n + 1$), which implies the desired conclusion.

As an example of the above, $43 = 2*21 + 1$ is a prime. Then $[43]_2 = 14$, so $43$ divides $2^{14} - 1$ which divides $2^{42} - 1 = (2^{21} - 1)(2^{21} + 1) $. In this case, $43$ divides $2^{21} + 1$.
penrose is offline  
July 23rd, 2018, 05:03 PM   #35
Newbie
 
Joined: Mar 2018
From: United States

Posts: 23
Thanks: 0

Continuing from the post above, we can say that if $2n+1$ is a prime, $[2n+1]_2$ divides $2n$. Furthermore, if $[2n+1]_2$ divides $n$, then $2n+1$ divides $2^n-1$, otherwise $2n+1$ divides $2^n+1$.
penrose is offline  
July 31st, 2018, 10:34 AM   #36
Newbie
 
Joined: Mar 2018
From: United States

Posts: 23
Thanks: 0

For the sake of completeness, we may as well observe that if $s$ is odd and $r$ divides $s$, then

$2^s + 1$ = ($2^r + 1$)($2^{s-r} - 2^{s-2r} + 2^{s-3r} - . . . . - 2^r + 1$)

So $2^r + 1$ divides $2^s + 1$

If we let $r$ = 1, then $2^1 + 1 = 3$ divides every Fermat-type number $2^s + 1$ for odd $s$, which is a special case we looked at earlier.
penrose is offline  
August 12th, 2018, 06:33 AM   #37
Newbie
 
Joined: Mar 2018
From: United States

Posts: 23
Thanks: 0

Suppose $p$ is a prime. The multiplicative group $1, 2, . . . . p-1$ (mod $p$) has $p-1$ elements, and let us assume (for now) that $p-1 = 2n$ with $n$ prime also. Subgroups (with more than the identity) can have $2, n,$ or $2n$ elements.

Then the squares of those numbers (mod $p$) form a subgroup of n elements, since $k^2 ≡ (p-k)^2$ mod $p$.

The number $2$ may or may not be in the group of squares. If it is, then the Mersenne Cycle $<p>_2$ also has $n$ elements, and $p$ divides $2^n-1$.

Corollary: Suppose $p = k^2 - 2$ is a prime and $n = (p-1)/2$ is a prime also. Then $p$ divides $2^n-1$.

For example, $5^2 - 2 = 23 = 2*11 + 1$, so $23$ divides $2^{11} - 1$.

Later we will remove some restrictions.
penrose is offline  
September 1st, 2018, 08:43 PM   #38
Newbie
 
Joined: Mar 2018
From: United States

Posts: 23
Thanks: 0

We are looking at $k^2 - 2$
Our objective is to find out which primes $p = 2n + 1$ have $2$ in their group of squares.

If $k$ is odd, then $k^2$ mod $8 ≡ 1$
$(1 - 2)$ mod $8 ≡ 7$
So $p ≡ 7$ mod $8$ and $n = (p-1) / 2 ≡ 3$ mod $4$

If k is even, then $k^2 ≡ 0$ or $≡ 4$ mod $16$

$0 - 2 ≡ 14$ mod $16$
$14 / 2 ≡ 7$ mod $8$
So $p ≡ 7$ mod $8$ and $n = (p-1) / 2 ≡ 3$ mod $4$

Or

$(4 - 2) ≡ 2$ mod $16$
$2 / 2 ≡ 1$ mod $8$
So $p ≡ 1$ mod $8$ and $n = (p-1) / 2 ≡ 0$ mod $4$

This should allow us to conclude the following:

Suppose $p = 2n + 1$ is a prime.
If $n ≡ 0$ or $n ≡ 3$ mod $4$, $p$ divides $2^n - 1$
If $n ≡ 1$ or $n ≡ 2$ mod $4$, $p$ divides $2^n + 1$
penrose is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
factoring, primes



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Particular primes : summed primes mobel Number Theory 2 September 21st, 2015 01:44 PM
Primes matheist Number Theory 3 October 30th, 2014 05:52 PM
primes and twin primes: Number between powers of 10 caters Number Theory 67 March 19th, 2014 04:32 PM
primes agustin975 Number Theory 11 March 10th, 2013 05:40 AM
# of primes billymac00 Number Theory 4 November 22nd, 2009 04:05 PM





Copyright © 2018 My Math Forum. All rights reserved.