Return to Answer

Let $n=2k>2$ be a Poulet number, then $k$ divides $2^{2k-1}-1$ (in particular, $k$ is odd) and we must prove that $q:=\frac{2^{2k-1}-1}k$ is composite.

Let $s$ be minimal positive integer for which $k$ divides $2^s-1$ (i.e., $s$ is a multiplicative order of 2 modulo $k$). Then all numbers $t$ for which $k$ divides $2^t-1$ are divisible by $s$. In particular, both $2k-1$ and $\varphi(k)$ are divisible by $s$, thus $s\leqslant \varphi(k)<k$, and $2k-1=sw$ for an integer $w\geqslant 3$. Therefore $$q=\frac{2^{sw}-1}k=\frac{2^s-1}k\cdot (1+2^s+\ldots+2^{(w-1)s}).$$ If $q$ is prime, the first multiple must be equal to 1. Thus $k=2^s-1$, and $$2^{sw}-1=qk=q(2^s-1).$$ But we may factorize $2^{sw}-1$ as $2^{sw}-1=\prod_{d|sw} \Phi_d(2)$, where $\Phi_n$ is $n$-th cyclotomic polynomial. For $d>1$ we get $\Phi_d(2)=\prod_{\xi}|2-\xi|>1$, where $\xi$ runs over primitive roots of unity of degree $d$. Thus $$ q=\frac{2^{sw}-1}{2^s-1}=\prod_{d\, \text{divides}\,sw\, \text{but not}\, s } \Phi_d(2) $$ is composite unless $sw$ has unique divisor not dividing $s$ (this divisor is of course $sw$). If $p$ is a prime divisor of $w$, and $q$ has a prime divisor $p_1\ne p$, then $sw/p_1$ would be another divisor of $sw$ not dividing $s$. Therefore both $w$ and $s$ are powers of the same prime $p$, and also $w=p$ (otherwise $ps$ is such an another divisor of $sw$).

To summarize, we get $w=p$ is prime, $s=p^j$ for certain integer $j\geqslant 1$, $k=2^s-1$ and $2^{p^j+1}-2=2^{s+1}-2=2k-1=sw=p^{j+1}$. But modulo $p$ we get $2^{p^j+1}\equiv 4$ that yields a contradiction.

Let $n=2k>2$ be a Poulet number, then $k$ divides $2^{2k-1}-1$ (in particular, $k$ is odd) and we must prove that $q:=\frac{2^{2k-1}-1}k$ is composite.

Let $s$ be minimal positive integer for which $k$ divides $2^s-1$ (i.e., $s$ is a multiplicative order of 2 modulo $k$). Then all numbers $t$ for which $k$ divides $2^t-1$ are divisible by $s$. In particular, both $2k-1$ and $\varphi(k)$ are divisible by $s$, thus $s\leqslant \varphi(k)<k$, and $2k-1=sw$ for an integer $w\geqslant 3$. Therefore $$q=\frac{2^{sw}-1}k=\frac{2^s-1}k\cdot (1+2^s+\ldots+2^{(w-1)s}).$$ If $q$ is prime, the first multiple must be equal to 1. Thus $k=2^s-1$, and $$2^{sw}-1=qk=q(2^s-1).$$ But we may factorize $2^{sw}-1$ as $2^{sw}-1=\prod_{d|sw} \Phi_d(2)$, where $\Phi_n$ is $n$-th cyclotomic polynomial. For $d>1$ we get $\Phi_d(2)=\prod_{\xi}|2-\xi|>1$, where $\xi$ runs over primitive roots of unity of degree $d$. Thus $$ q=\frac{2^{sw}-1}{2^s-1}=\prod_{d\, \text{divides}\,sw\, \text{but not}\, s } \Phi_d(2) $$ is composite unless $sw$ has unique divisor not dividing $s$ (this divisor is of course $sw$). If $s$ has a prime divisor $p\ne w$, then $sw/p$ would be another divisor of $sw$ not dividing $s$.

Therefore $w$ is prime and $s=w^j$ for certain integer $j\geqslant 1$, $k=2^s-1$ and $2^{w^j+1}-2=2^{s+1}-2=2k-1=sw=w^{j+1}$. But modulo $w$ we get $2^{w^j+1}\equiv 4$ that yields a contradiction.

Let $n=2k>2$ be a Poulet number, then $k$ divides $2^{2k-1}-1$ (in particular, $k$ is odd) and we must prove that $q:=\frac{2^{2k-1}-1}k$ is composite.

Let $s$ be minimal positive integer for which $k$ divides $2^s-1$ (i.e., $s$ is a multiplicative order of 2 modulo $k$). Then all numbers $t$ for which $k$ divides $2^t-1$ are divisible by $s$. In particular, both $2k-1$ and $\varphi(k)$ are divisible by $s$, thus $s\leqslant \varphi(k)<k$, and $2k-1=sw$ for an integer $w\geqslant 3$. Therefore $$q=\frac{2^{sw}-1}k=\frac{2^s-1}k\cdot (1+2^s+\ldots+2^{(w-1)s}).$$ If $q$ is prime, the first multiple must be equal to 1. Thus $k=2^s-1$, and $$2^{sw}-1=qk=q(2^s-1).$$ But we may factorize $2^{sw}-1$ as $2^{sw}-1=\prod_{d|sw} \Phi_d(2)$, where $\Phi_n$ is $n$-th cyclotomic polynomial. For $d>1$ we get $\Phi_d(2)=\prod_{\xi}|2-\xi|>1$, where $\xi$ runs over primitive roots of unity of degree $d$. Thus $$ q=\frac{2^{sw}-1}{2^s-1}=\prod_{d\, \text{divides}\,sw\, \text{but not}\, s } \Phi_d(2) $$ is composite unless $sw$ has unique divisor not dividing $s$ (this divisor is of course $sw$). If $p$ is a prime divisor of $w$, and $q$ has a prime divisor $p_1\ne p$, then $sw/p_1$ would be another divisor of $sw$ not dividing $s$. Therefore both $w$ and $s$ are powers of the same prime $p$, and also $w=p$ (otherwise $ps$ is such an another divisor of $sw$).

To summarize, we get $w=p$ is prime, $s=p^j$ for certain integer $j\geqslant 1$, $k=2^s-1$ and $2^{p^j+1}-2=2^{s+1}-2=2k-1=sw=p^{j+1}$. But nodulo $p$ we get $2^{p^j+1}\equiv 4$ that yields a contradiction.

Let $n=2k>2$ be a Poulet number, then $k$ divides $2^{2k-1}-1$ (in particular, $k$ is odd) and we must prove that $q:=\frac{2^{2k-1}-1}k$ is composite.

Let $s$ be minimal positive integer for which $k$ divides $2^s-1$ (i.e., $s$ is a multiplicative order of 2 modulo $k$). Then all numbers $t$ for which $k$ divides $2^t-1$ are divisible by $s$. In particular, both $2k-1$ and $\varphi(k)$ are divisible by $s$, thus $s\leqslant \varphi(k)<k$, and $2k-1=sw$ for an integer $w\geqslant 3$. Therefore $$q=\frac{2^{sw}-1}k=\frac{2^s-1}k\cdot (1+2^s+\ldots+2^{(w-1)s}).$$ If $q$ is prime, the first multiple must be equal to 1. Thus $k=2^s-1$, and $$2^{sw}-1=qk=q(2^s-1).$$ But we may factorize $2^{sw}-1$ as $2^{sw}-1=\prod_{d|sw} \Phi_d(2)$, where $\Phi_n$ is $n$-th cyclotomic polynomial. For $d>1$ we get $\Phi_d(2)=\prod_{\xi}|2-\xi|>1$, where $\xi$ runs over primitive roots of unity of degree $d$. Thus $$ q=\frac{2^{sw}-1}{2^s-1}=\prod_{d\, \text{divides}\,sw\, \text{but not}\, s } \Phi_d(2) $$ is composite unless $sw$ has unique divisor not dividing $s$ (this divisor is of course $sw$). If $p$ is a prime divisor of $w$, and $q$ has a prime divisor $p_1\ne p$, then $sw/p_1$ would be another divisor of $sw$ not dividing $s$. Therefore both $w$ and $s$ are powers of the same prime $p$, and also $w=p$ (otherwise $ps$ is such an another divisor of $sw$).

To summarize, we get $w=p$ is prime, $s=p^j$ for certain integer $j\geqslant 1$, $k=2^s-1$ and $2^{p^j+1}-2=2^{s+1}-2=2k-1=sw=p^{j+1}$. But modulo $p$ we get $2^{p^j+1}\equiv 4$ that yields a contradiction.

Let $n=2k$ be a Poulet number, then $k$ divides $2^{2k-1}-1$ (in particular, $k$ is odd) and we must prove that $q:=\frac{2^{2k-1}-1}k$ is composite.

Let $s$ be minimal positive integer for which $k$ divides $2^s-1$ (i.e., $s$ is a multiplicative order of 2 modulo $k$). Then all numbers $t$ for which $k$ divides $2^t-1$ are divisible by $s$. In particular, both $2k-1$ and $\varphi(k)$ are divisible by $s$, thus $s\leqslant \varphi(k)<k$, and $2k-1=sw$ for an integer $w\geqslant 3$. Therefore $$q=\frac{2^{sw}-1}k=\frac{2^s-1}k\cdot (1+2^s+\ldots+2^{(w-1)s}).$$ If $q$ is prime, the first multiple must be equal to 1. Thus $k=2^s-1$, and $$2^{sw}-1=qk=q(2^s-1).$$ But we may factorize $2^{sw}-1$ as $2^{sw}-1=\prod_{d|sw} \Phi_d(2)$, where $\Phi_n$ is $n$-th cyclotomic polynomial. For $d>1$ we get $\Phi_d(2)=\prod_{\xi}|2-\xi|>1$, where $\xi$ runs over primitive roots of unity of degree $d$. Thus $$ q=\frac{2^{sw}-1}{2^s-1}=\prod_{d\, \text{divides}\,sw\, \text{but not}\, s } \Phi_d(2) $$ is composite unless $sw$ has unique divisor not dividing $s$ (this divisor is of course $sw$). If $p$ is a prime divisor of $w$, and $q$ has a prime divisor $p_1\ne p$, then $sw/p_1$ would be another divisor of $sw$ not dividing $s$. Therefore both $w$ and $s$ are powers of the same prime $p$, and also $w=p$ (otherwise $ps$ is such an another divisor of $sw$).

To summarize, we get $w=p$ is prime, $s=p^j$ for certain integer $j\geqslant 1$, $k=2^s-1$ and $2^{p^j+1}-2=2^{s+1}-2=2k-1=sw=p^{j+1}$. But nodulo $p$ we get $2^{p^j+1}\equiv 4$ that yields a contradiction.

Let $n=2k>2$ be a Poulet number, then $k$ divides $2^{2k-1}-1$ (in particular, $k$ is odd) and we must prove that $q:=\frac{2^{2k-1}-1}k$ is composite.

Let $s$ be minimal positive integer for which $k$ divides $2^s-1$ (i.e., $s$ is a multiplicative order of 2 modulo $k$). Then all numbers $t$ for which $k$ divides $2^t-1$ are divisible by $s$. In particular, both $2k-1$ and $\varphi(k)$ are divisible by $s$, thus $s\leqslant \varphi(k)<k$, and $2k-1=sw$ for an integer $w\geqslant 3$. Therefore $$q=\frac{2^{sw}-1}k=\frac{2^s-1}k\cdot (1+2^s+\ldots+2^{(w-1)s}).$$ If $q$ is prime, the first multiple must be equal to 1. Thus $k=2^s-1$, and $$2^{sw}-1=qk=q(2^s-1).$$ But we may factorize $2^{sw}-1$ as $2^{sw}-1=\prod_{d|sw} \Phi_d(2)$, where $\Phi_n$ is $n$-th cyclotomic polynomial. For $d>1$ we get $\Phi_d(2)=\prod_{\xi}|2-\xi|>1$, where $\xi$ runs over primitive roots of unity of degree $d$. Thus $$ q=\frac{2^{sw}-1}{2^s-1}=\prod_{d\, \text{divides}\,sw\, \text{but not}\, s } \Phi_d(2) $$ is composite unless $sw$ has unique divisor not dividing $s$ (this divisor is of course $sw$). If $p$ is a prime divisor of $w$, and $q$ has a prime divisor $p_1\ne p$, then $sw/p_1$ would be another divisor of $sw$ not dividing $s$. Therefore both $w$ and $s$ are powers of the same prime $p$, and also $w=p$ (otherwise $ps$ is such an another divisor of $sw$).

To summarize, we get $w=p$ is prime, $s=p^j$ for certain integer $j\geqslant 1$, $k=2^s-1$ and $2^{p^j+1}-2=2^{s+1}-2=2k-1=sw=p^{j+1}$. But nodulo $p$ we get $2^{p^j+1}\equiv 4$ that yields a contradiction.