My Math Forum Primes and Factoring
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

June 17th, 2018, 01:44 PM   #31
Newbie

Joined: Mar 2018
From: United States

Posts: 19
Thanks: 0

Quote:
 Originally Posted by penrose 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 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

June 18th, 2018, 01:17 AM   #32
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 204
Thanks: 60

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
 Originally Posted by penrose 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.

July 18th, 2018, 04:45 AM   #33
Newbie

Joined: Mar 2018
From: United States

Posts: 19
Thanks: 0

Quote:
 Originally Posted by penrose 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.

July 19th, 2018, 05:03 PM   #34
Newbie

Joined: Mar 2018
From: United States

Posts: 19
Thanks: 0

Quote:
 Originally Posted by penrose 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$.

 Tags factoring, primes

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top