Does there exist a natural number $n \geq 2$ such that: a) $\frac{2^{n-1}+1}{n}$ is a natural number? b) $\frac{2^{2n-1}-1}{n}$ is a prime number?
Problem
Source: XII International Festival of Young Mathematicians Sozopol 2023, Theme for 10-12 grade
Tags: number theory
23.09.2024 23:04
Part (a). I claim there are no such $n$. Suppose the contrary and notice that any such $n$ is necessarily odd, let $k\triangleq v_2(n-1)$. Let $p\mid n$ be an arbitrary prime. Then, $2^{n-1}\equiv -1\pmod{p}$ and $2^{2(n-1)}\equiv 1\pmod{p}$. Setting $d$ to be the smallest positive integer such that $p\mid 2^d-1$, we find $d\nmid n-1$ and $d\mid 2(n-1)$. So, $v_2(d)=1+k$. Since $d\mid p-1$ as well (by Fermat), we have $2^{k+1}\mid p-1$. As this is true for any $p\mid n$, we conclude $n\equiv 1\pmod{2^{k+1}}$, contradicting with the fact $v_2(n-1)=k$. Part (b). Suppose the contrary that $2^{2n-1} -1= np$ for some prime $p$. Notice if $2n-1$ is a prime, then $2^{2n-1}\equiv 1\pmod{n}$ yields $d=2n-1$ where $d$ is the smallest positive integer such that $n\mid 2^d-1$ (as $d\mid 2n-1$). But then $2n-1=d\mid \varphi(n)$ by Euler's theorem, a contradiction. So, $2n-1$ is not a prime. Let $d$ be the smallest positive integer for which $n\mid 2^d-1$. We then have $2n-1=dq$ for some $q$. Now if $n<2^d-1$ then it's immediate that the ratio is not a prime, so suppose $n=2^d-1$. If $q$ is not a prime, then setting $q=q_1q_2$ for $q_1>q_2$, we find that \[ 2^{2n-1}-1 = (2^{dq_1}-1)((2^{dq_1})^{q_2-1}+\cdots+1)=(2^d-1)(2^{d(q_1-1)}+\cdots+1)((2^{dq_1})^{q_2-1}+\cdots+1), \]so $2^{2n-1}-1/(2^d-1)$ has two factors larger than 1. Thus, $2n-1=dq$. Now if $q\nmid d$ then $(2^d-1,2^q-1)=2^{(d,q)}-1=1$ yields $2^{2n-1}-1=(2^d-1)(2^q-1)t$ where $t=(2^{2n-1}-1)/((2^d-1)(2^q-1))$, so the ratio is not a prime. Lastly, let $2n-1=dq$ and $q\mid d$. Then $2n-1\le d^2$. At the same time $n=2^d-1$, so $2^{d+1}\le d^2+3$. From here we obtain no solutions. So, the ratio is never a prime.