My Math Forum  

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

Number Theory Number Theory Math Forum


Thanks Tree10Thanks
Reply
 
LinkBack Thread Tools Display Modes
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
johng40 is offline  
 
April 3rd, 2018, 08:06 AM   #12
Newbie
 
Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
Originally Posted by johng40 View Post
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.
penrose is offline  
April 4th, 2018, 05:34 PM   #13
Newbie
 
Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
Originally Posted by Maschke View Post
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.
penrose is offline  
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.
penrose is offline  
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 View Post
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.
Thanks from Adam Ledger

Last edited by cjem; April 8th, 2018 at 09:38 AM.
cjem is offline  
April 9th, 2018, 06:47 PM   #16
Newbie
 
Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
Originally Posted by cjem View Post
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?
penrose is offline  
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 View Post
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.
cjem is offline  
April 13th, 2018, 03:08 PM   #18
Newbie
 
Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
Originally Posted by cjem View Post
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$
penrose is offline  
April 16th, 2018, 01:57 PM   #19
Newbie
 
Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
Originally Posted by penrose View Post
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 View Post
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$.
penrose is offline  
April 20th, 2018, 05:45 AM   #20
Newbie
 
Joined: Mar 2018
From: United States

Posts: 24
Thanks: 2

Quote:
Originally Posted by penrose View Post
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 View Post
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)?
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.