My Math Forum Primes and Factoring

 Number Theory Number Theory Math Forum

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

Joined: Mar 2018
From: United States

Posts: 28
Thanks: 2

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: 311
Thanks: 109

Math Focus: Number Theory, Algebraic 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: 28
Thanks: 2

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: 28
Thanks: 2

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$.

 July 23rd, 2018, 05:03 PM #35 Newbie   Joined: Mar 2018 From: United States Posts: 28 Thanks: 2 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$.
 July 31st, 2018, 10:34 AM #36 Newbie   Joined: Mar 2018 From: United States Posts: 28 Thanks: 2 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. Thanks from Ak23
 August 12th, 2018, 06:33 AM #37 Newbie   Joined: Mar 2018 From: United States Posts: 28 Thanks: 2 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 $_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. Thanks from Ak23

 September 1st, 2018, 08:43 PM #38 Newbie   Joined: Mar 2018 From: United States Posts: 28 Thanks: 2 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$
 September 23rd, 2018, 10:55 AM #39 Newbie   Joined: Mar 2018 From: United States Posts: 28 Thanks: 2 This is a bit of an aside. It has previously been mentioned that every Fermat Type number $n = 2^k + 1$ for odd $k$ is divisible by $3$. In general, if you have a number $2^{k_r} + 2^{k_{r-1}} + . . . + 2^{k_0}$, then count the number of even and odd exponents (count mod $3$). If they are equal, the number can be divided by $3$. A Fermat Type number $n = 2^k + 2^0$ for odd $k$ has one odd and one even exponent.
 October 21st, 2018, 05:13 PM #40 Newbie   Joined: Mar 2018 From: United States Posts: 28 Thanks: 2 Factoring a number When factoring an arbitrary number, one can use the Mersenne index ($length$ of the $2-cycle$) to help. Naturally, you have to know what it is. I won't address that particular problem right now. Recall that we designated this index by $[n]_2$ for odd $n$. Suppose we want to factor $35$. The Mersenne index is $12$. I know this because I already know that $35$ = $5$ $x$ $7$, and it happens that $[35]_2$ = $LCM([5]_2, [7]_2)$. Since $[5]_2$ = $4$ $and$ $[7]_2$ = $3$, $LCM(4,3) = 12$. Therefore the divisors of $35$ must be contained within $2^{12}-1$. Since $2^{12}-1 = (2^3-1)(2^3+1)(2^6+1)$,we start with $2^3-1 = 7$. And, we can stop there.

 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