Does there exist a natural number n≥2 such that: a) 2n−1+1n is a natural number? b) 22n−1−1n 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≜. 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.