3
$\begingroup$

If positive integer $n$ such $n\mid2^n-2$,where $n>1$, we called $n$ is Poulet number, see: https://en.wikipedia.org/wiki/Super-Poulet_number

I found if $n>2$ is Poulet number, then $\dfrac{2^n-2}{n}$ always is composite number

Is this a known result? if $n$ is odd number, so $\frac{2^n-2}{n}$ is even number, and $\frac{2^n-2}{n}>2$,so $\frac{2^n-2}{n}$ is composite number.

But for $n$ is even number. I can't prove it

$\endgroup$
5
  • 2
    $\begingroup$ Since my earlier comment implicitly making this point has been deleted, I will note explicitly that $n=2$ is an exception, because $\frac{2^2 - 2}{2} = 1$ is not composite. $\endgroup$ Commented Sep 15, 2021 at 10:02
  • 13
    $\begingroup$ This happens to be a problem from an high-school olympiad in China, just a few days ago: artofproblemsolving.com/community/c6h2669914. I'd be surprised to find that this is a coincidence... ;) $\endgroup$ Commented Sep 15, 2021 at 15:36
  • 1
    $\begingroup$ Also, strictly speaking you are missing out on the case $n=3$ so the correct condition should be $n \ge 4$. $\endgroup$ Commented Sep 15, 2021 at 15:38
  • $\begingroup$ what is the purpose of this bounty? $\endgroup$ Commented Sep 18, 2021 at 13:14
  • $\begingroup$ I want to konw have paper reseach this problem? $\endgroup$
    – math110
    Commented Sep 18, 2021 at 13:18

1 Answer 1

17
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Nice,+1.so this is old result?Thanks $\endgroup$
    – math110
    Commented Sep 15, 2021 at 14:51
  • $\begingroup$ No idea. In any case it is quite standard. $\endgroup$ Commented Sep 15, 2021 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .