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 factorizatgion of Mersenne numbers There is a great deal of effort going on to find Mersenne primes.

penrose

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

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

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.

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

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?

cjem

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.

penrose

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

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

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)?