# Relations between coefficient and exponent of Proth prime form $k\cdot 2^n+1$?

Definition: Proth number is a number of the form :

$$k\cdot 2^n+1$$

where $k$ is an odd positive integer and $n$ is a positive integer such that : $2^n>k$

My question : If Proth number is prime number are there some other known relations in addition to $2^n>k$ , between exponent $n$ and coefficient $k$ ?

-

There are many simple relationships that involve congruences. They have a flavour much like results you have mentioned in earlier posts.

For example, if $n>1$ is odd, then $k$ must be of the form $6a-1$ or $6a+3$. If $n$ is even, then $k$ must be of the form $6a+1$ or $6a+3$. The arguments are the familiar ones. For example, if $n$ is odd, then since $2\equiv -1\pmod 3$, it follows that $2^n\equiv (-1)^n =-1\pmod{3}$. But if $k$ is of the form $6a+1$, it follows that $k2^n \equiv -1 \pmod{3}$, and therefore $k2^n \equiv 0\pmod{3}$. If $n>1$, this means that $k2^n+1$ cannot be prime, since it is greater than $3$ and divisible by $3$.

We can obtain similar restrictions by working modulo primes greater than $3$. For example, suppose that $n \equiv 2\pmod {4}$, that is, $n$ is of the form $4a+2$. Then $2^n \equiv 4 \pmod {5}$, and therefore if $k \equiv 1\pmod {5}$, we have $k2^n +1\equiv 4+1=5 \pmod{5}$. This is impossible unless $n=2$ (and therefore $k=1$). So we conclude that if $n$ is of the form $4a+2$, and $k2^n+1$ is prime, then $k$ cannot be of the form $10b+1$ except in the case $n=2$, $k=1$. We can obtain similar restrictions on $k$ if $n$ is of the form $4a$, also $4a+1$, also $4a+3$.

Added: In a comment, the OP asks for a proof that if $k\equiv 1\pmod 3$ and $k\equiv 1\pmod{10}$ (and $k2^n+1$ is prime), then $n\equiv 0\pmod 4$. This is not absolutely true, take $n=2$, $k=1$, but let's not worry about isolated exceptions at the beginning. We need to rule out the other possibilities for $n$.

By the contents of the answer above, $n\equiv 2\pmod{4}$ is ruled out apart from a single exception. Now we need to rule out $n \equiv 1$ and $n\equiv 3$ (modulo $4$). That would make $n$ odd. In that case, again by the answer above, $2^n \equiv -1\pmod{3}$. So if $k \equiv 1\pmod{3}$, we find that $k2^n+1\equiv 0\pmod{3}$. With the single exception of $k=1$, $n=1$, this means that $k2^n+1$ cannot be prime.

-
,I understand first part of your answer, for the second part : $11 \cdot 2^6 \not \equiv 5 \pmod 5$,$704\equiv 4 \pmod 5$ –  pedja Nov 18 '11 at 13:20
@pedja: Sorry, typo, it was supposed to be $k2^n+1 \equiv 4+1=5\pmod{5}$. And $k2^n+1$ is what we are worried about primality of. –  André Nicolas Nov 18 '11 at 16:52
@pedja: I added some stuff at the end of the previous answer, since it was a bit long for a comment. The result follows fairly quickly from stuff that was already in the answer. –  André Nicolas Nov 18 '11 at 18:36
,Yes I see,thanks for edit..I deleted comment because I have proved statement slightly different than you... –  pedja Nov 18 '11 at 18:39