My Math Forum Primes and Factoring

 Number Theory Number Theory Math Forum

 April 2nd, 2018, 04:28 PM #11 Member   Joined: Jan 2016 From: Athens, OH Posts: 89 Thanks: 47 You are asking about Mersenne primes or more generally Mersenne numbers - https://en.wikipedia.org/wiki/Mersen...rsenne_numbers That is for a prime p, a number of the form $2^p-1$. Your "next" prime is the smallest prime divisor of $2^p-1$. See the small table in Wikipedia of the factorizatgion of Mersenne numbers There is a great deal of effort going on to find Mersenne primes. Thanks from Maschke and Adam Ledger
April 3rd, 2018, 08:06 AM   #12
Newbie

Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
 Originally Posted by johng40 You are asking about Mersenne primes or more generally Mersenne numbers - https://en.wikipedia.org/wiki/Mersen...rsenne_numbers That is for a prime p, a number of the form $2^p-1$. Your "next" prime is the smallest prime divisor of $2^p-1$. See the small table in Wikipedia of the factorization of Mersenne numbers There is a great deal of effort going on to find Mersenne primes.
This is correct. The length of the 2-cycle of n is the exponent m of the smallest Mersenne number 2^m - 1 which n divides.

So, the length of the 2-cycle for a Mersenne number 2^m-1 is just m. The length of the 2-cycle for a Fermat type number 2^m+1 is 2*m. Thus for every positive m there is a least one number whose 2-cycle has length m, namely the Mersenne number 2^m-1.

We can formalize this by collecting for each m the ascending sequence of numbers whose 2-cycles have length m. Every such sequence terminates with the Mersenne number 2^m-1. If the Mersenne number is the only one in the sequence, it is a prime.

If m = p is a prime number, then the first number in the sequence for p will have to be the smallest prime divisor of 2^p-1. As was pointed out above, this was how I was choosing my next prime.

April 4th, 2018, 05:34 PM   #13
Newbie

Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
 Originally Posted by Maschke optimizing my program
If p is a prime, the smallest prime divisor of the Mersenne number 2^p-1 is of the form 2*p*k + 1, k odd

Starting with 11,
23=2*11+1
47=2*23+1
2351=2*47*25+1
4703=2*2351+1

Last edited by penrose; April 4th, 2018 at 05:57 PM.

 April 8th, 2018, 08:37 AM #14 Newbie   Joined: Mar 2018 From: United States Posts: 24 Thanks: 2 Every Mersenne number has an associated Fermat-type number. 2^n - 1 and 2^n + 1 Is the following true? A Fermat-type number 2^n+1, n odd, is always divisible by 3. Last edited by penrose; April 8th, 2018 at 08:43 AM.
April 8th, 2018, 09:09 AM   #15
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 264
Thanks: 79

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
 Originally Posted by penrose Is the following true? A Fermat-type number 2^n+1, n odd, is always divisible by 3.
Yes. Note that $4 \equiv 1 \pmod 3$, so all powers of $4$ are also $1 \pmod 3$. So $2^{2k+1} + 1= 2 \times 4^k + 1\equiv 2 \times 1 + 1 \equiv 0 \pmod 3$. i.e. $3$ divides $2^{2k+1} + 1$. As a result, if $n$ is odd, then $2^n - 1$ is never divisible by $3$, being $2$ less than a multiple of 3.

The reverse holds if $n$ is even: $2^n - 1$ is always divisible by $3$ while $2^n + 1$ never is.

Last edited by cjem; April 8th, 2018 at 09:38 AM.

April 9th, 2018, 06:47 PM   #16
Newbie

Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
 Originally Posted by cjem Yes. Note that $4 \equiv 1 \pmod 3$, so all powers of $4$ are also $1 \pmod 3$. So $2^{2k+1} + 1= 2 \times 4^k + 1\equiv 2 \times 1 + 1 \equiv 0 \pmod 3$. i.e. $3$ divides $2^{2k+1} + 1$.
Nice! Can we generalize that?

Is $2^{2^k n}+ 1$, n odd, n > 1, divisible by $2^{2^k }+ 1$

In words, is every Fermat-type number divisible by a Fermat number?

April 10th, 2018, 04:06 AM   #17
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 264
Thanks: 79

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
 Originally Posted by penrose Nice! Can we generalize that? Is $2^{2^k n}+ 1$, n odd, n > 1, divisible by $2^{2^k }+ 1$ In words, is every Fermat-type number divisible by a Fermat number?
Yes, and a similar idea works to prove it. If $n$ is odd, then $n = 1 + 2r$ for some integer $r$. We have

$2^{2^k n} +1 = 2^{2^k (1 + 2r)} +1 = 2^{2^k} \times 2^{2^k 2r} = 2^{2^k} \times 2^{2^{k+1} r} + 1 \\ \qquad = 2^{2^k} \times \left(2^{2^{k+1}}\right)^r + 1$

Now, if we can show that $\left(2^{2^{k+1}}\right)^r$ is congruent to $1 \pmod{2^{2^k} + 1}$, we'll be done. Indeed, this will imply

$2^{2^k n} +1 = 2^{2^k} \times \left(2^{2^{k+1}}\right)^r + 1 \equiv 2^{2^k} \times 1 + 1 \equiv 0 \pmod {2^{2^k} + 1}$,

which means precisely that $2^{2^k n} +1$ is divisible by $2^{2^k} + 1$.

So let's show it:

Firstly observe that $2^{2^{k+1}} - 1 = (2^{2^k} - 1)(2^{2^k} + 1)$ is a multiple of $(2^{2^k} + 1)$. That is,

$2^{2^{k+1}} - 1 \equiv 0 \pmod {2^{2^k} + 1}$,

i.e.

$2^{2^{k+1}} \equiv 1 \pmod {2^{2^k} + 1}$.

But now raising both sides to the power of $r$ gives us what we wanted.

April 13th, 2018, 03:08 PM   #18
Newbie

Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
 Originally Posted by cjem The reverse holds if $n$ is even: $2^n - 1$ is always divisible by $3$ while $2^n + 1$ never is.
Looks good.

Expanding on this by example, suppose we start with $2^{28} - 1$.

Then $2^{28} - 1 = (2^{14} - 1)(2^{14} + 1) = (2^{7} - 1)(2^{7} + 1)(2^{14} + 1)$

Is the following true?

Every Mersenne number can be factored into the product of a leading Mersenne number with an odd exponent followed a sequence of Fermat type numbers with increasing even orders. Furthermore, the resulting factor sets form a disjoint partition of the full factor space.

In the above,

$2^{7} - 1 = 127$
$2^{7} + 1 = 3*43$
$2^{14} + 1 = 5*29*113$

April 16th, 2018, 01:57 PM   #19
Newbie

Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
 Originally Posted by penrose Nice! Can we generalize that? Is $2^{2^k n}+ 1$, n odd, n > 1, divisible by $2^{2^k }+ 1$ In words, is every Fermat-type number divisible by a Fermat number?
Quote:
 Originally Posted by cjem Yes, and a similar idea works to prove it.
Excellent! As an aside, we might observe that since "divisibility" is a base independent property, we should be able to expand the above to:

$a^{2^k n}+ 1$, a > 1, n odd, n > 1, is divisible by $a^{2^k }+ 1$

Example: Show that 1729 is divisible by 13.

Since $1729 = 12^3 + 1$, it is divisible by $12 + 1 = 13$.

April 20th, 2018, 05:45 AM   #20
Newbie

Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
 Originally Posted by penrose Every Mersenne number has an associated Fermat-type number. 2^n - 1 and 2^n + 1 Is the following true? A Fermat-type number 2^n+1, n odd, is always divisible by 3.
Quote:
 Originally Posted by cjem Yes. Note that $4 \equiv 1 \pmod 3$, so all powers of $4$ are also $1 \pmod 3$. So $2^{2k+1} + 1= 2 \times 4^k + 1\equiv 2 \times 1 + 1 \equiv 0 \pmod 3$. i.e. $3$ divides $2^{2k+1} + 1$.
Now I want to revisit this proof using induction.

Consider the assertion that $2^n + 1 = 3S_n$ for odd n. This is certainly true for n = 1. If true for a given odd n, then

$............................................. 2^{n + 2} + 1 = 2^2*2^n + 1$
$................................................. ..... = 2^2*(3S_n - 1) + 1$
$................................................. ..... = 3(2^2S_n - 1)$

Thus it is true for all odd n. It provides us with an inductive definition of the 'other factor' when we actually divide out the 3, which could be useful in the future.

$................................................. .S_{n+2} = 2^2S_n - 1$

Does that proof look okay (other than the fact that I don't know how to indent and line up equations)?

 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