June 17th, 2018, 02:44 PM  #31  
Newbie Joined: Mar 2018 From: United States Posts: 27 Thanks: 2  Quote:
. The following identities are mod ($2p+1$): . Case 1: If $2p+1$ divides $2^p1$, . $2^p ≡ 1$ . $2^{p1}$ ≡ $p+1$ . $(2^{(p1)/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^{p1}$ ≡ $p$ . $(2^{(p1)/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, 02:17 AM  #32 
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 282 Thanks: 85 Math Focus: Algebraic Number Theory, Arithmetic Geometry  
July 18th, 2018, 05:45 AM  #33  
Newbie Joined: Mar 2018 From: United States Posts: 27 Thanks: 2  Quote:
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 $n1$ 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, 06:03 PM  #34  
Newbie Joined: Mar 2018 From: United States Posts: 27 Thanks: 2  Quote:
Finally, we need to know that if $r$ is a divisor of $s$, then $2^r  1$ divides $2^s1$. 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, 06:03 PM  #35 
Newbie Joined: Mar 2018 From: United States Posts: 27 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^n1$, otherwise $2n+1$ divides $2^n+1$.

July 31st, 2018, 11:34 AM  #36 
Newbie Joined: Mar 2018 From: United States Posts: 27 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^{sr}  2^{s2r} + 2^{s3r}  . . . .  2^r + 1$) So $2^r + 1$ divides $2^s + 1$ If we let $r$ = 1, then $2^1 + 1 = 3$ divides every Fermattype number $2^s + 1$ for odd $s$, which is a special case we looked at earlier. 
August 12th, 2018, 07:33 AM  #37 
Newbie Joined: Mar 2018 From: United States Posts: 27 Thanks: 2 
Suppose $p$ is a prime. The multiplicative group $1, 2, . . . . p1$ (mod $p$) has $p1$ elements, and let us assume (for now) that $p1 = 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 ≡ (pk)^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^n1$. Corollary: Suppose $p = k^2  2$ is a prime and $n = (p1)/2$ is a prime also. Then $p$ divides $2^n1$. For example, $5^2  2 = 23 = 2*11 + 1$, so $23$ divides $2^{11}  1$. Later we will remove some restrictions. 
September 1st, 2018, 09:43 PM  #38 
Newbie Joined: Mar 2018 From: United States Posts: 27 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 = (p1) / 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 = (p1) / 2 ≡ 3$ mod $4$ Or $(4  2) ≡ 2$ mod $16$ $2 / 2 ≡ 1$ mod $8$ So $p ≡ 1$ mod $8$ and $n = (p1) / 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, 11:55 AM  #39 
Newbie Joined: Mar 2018 From: United States Posts: 27 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_{r1}} + . . . + 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, 06:13 PM  #40 
Newbie Joined: Mar 2018 From: United States Posts: 27 Thanks: 2  Factoring a number
When factoring an arbitrary number, one can use the Mersenne index ($length$ of the $2cycle$) 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^31)(2^3+1)(2^6+1)$, we start with $2^31 = 7$. And, we can stop there.


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 02:44 PM 
Primes  matheist  Number Theory  3  October 30th, 2014 06:52 PM 
primes and twin primes: Number between powers of 10  caters  Number Theory  67  March 19th, 2014 05:32 PM 
primes  agustin975  Number Theory  11  March 10th, 2013 06:40 AM 
# of primes  billymac00  Number Theory  4  November 22nd, 2009 05:05 PM 