![]() |
April 2nd, 2018, 04:28 PM | #11 |
Member Joined: Jan 2016 From: Athens, OH Posts: 86 Thanks: 44 |
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. |
![]() |
April 3rd, 2018, 08:06 AM | #12 | |
Newbie Joined: Mar 2018 From: United States Posts: 11 Thanks: 0 | Quote:
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: 11 Thanks: 0 | 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: 11 Thanks: 0 |
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: 169 Thanks: 52 Math Focus: Algebraic Number Theory, Arithmetic Geometry | Quote:
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: 11 Thanks: 0 | Quote:
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: 169 Thanks: 52 Math Focus: Algebraic Number Theory, Arithmetic Geometry | Quote:
$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: 11 Thanks: 0 | Quote:
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: 11 Thanks: 0 | Quote:
$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: 11 Thanks: 0 | Quote:
Quote:
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 | |
|
![]() | ||||
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 |