4
$\begingroup$

Show that $(k+1) \nmid 2^{k}+1$ for any $k\in \mathbb{N}$

I had found out this question from somewhere and here's my solution. I am not sure if I am missing out something in the solution. Please check if it's correct.

My partial solution (not sure if it adds any value) :

If $k$ is odd there's a clear contradiction since an even number can't divide an odd number, which shows $k$ is even.

This shows that $k+1$ is odd, meaning, it has got all odd prime divisors. Let $p$ be an odd prime dividing it. Since $k$ is even, observe that $2^{k}$ is a squared number and $2^{k}\equiv -1 \pmod{p}$. By the theorem stated here we see that $p = 4x+1$ for some $x$. This shows that each and every odd prime factor of $k+1$ is of the form $4j+1$ and so is $k+1$.

And I couldn't proceed anymore!

|cite|improve this question
$\endgroup$
  • $\begingroup$ See for the similar question here. $\endgroup$ – Dietrich Burde Apr 15 '18 at 15:05
2
$\begingroup$

You are on the right track. If $k$ is odd there is no way that $(k+1)$ is a divisor of $2^k+1$, so $k$ is even. If $k$ is even all the prime divisors of $2^k+1$ are of the form $4j+1$, hence $k$ is a multiple of $4$, say $k=4m$. All the prime divisors of $$ 2^{4m}+1 = \Phi_8(2^m) $$ are $\equiv 1\pmod{8}$, hence $k$ is a multiple of $8$, say $k=8n$. All the prime divisors of $$ 2^{8n}+1 = \Phi_{16}(2^n) $$ are $\equiv 1\pmod{16}$, hence $k$ is a multiple of $16$ etcetera, this process never stops.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ .Having little knowledge in number theory I would like to learn what does the $\Phi_8(2^m)$ signify? I have got your solution almost except the notations $2^{4m}+1 = \Phi_8(2^m)$ and $2^{8n}+1 = \Phi_{16}(2^n)$. (+1) $\endgroup$ – vbm Apr 15 '18 at 15:36
  • $\begingroup$ @thevbm: $\Phi_n(x)$ is the $n$-th cyclotomic polynomial, i.e. the minimal polynomial of a primitive $n$-th root of unity, with degree $\varphi(n)$. $\endgroup$ – Jack D'Aurizio Apr 15 '18 at 15:51
  • 2
    $\begingroup$ Cyclotomic polynomials give an elementary proof of the existence of infinite primes $\equiv 1\pmod{n}$: the very same idea is exploited in my proof. $\endgroup$ – Jack D'Aurizio Apr 15 '18 at 15:52
  • $\begingroup$ Thank you for this clear explanation. $\endgroup$ – vbm Apr 15 '18 at 15:54
1
$\begingroup$

First of all, $k$ is even. We multiply $2$ to the right factor. Suppose that $k+1|2^{k+1}+2$. Then, $2^{k+1}+2-2(k+1)$ is also a multiple of $k+1$. We consider a maximum odd prime divisor of $k+1$. Denote it by $p$. With use of the binomial theorem, $2^{k+1}+2-2(k+1)$= the summation of $k+1$; choose $i$ from $2$ to $k-1$ and $2$, we can observe that $k+1$; choose $i$ (for $i=2,..,k-1$) is a multiple of $p$ with small computation. Therefore, $p|k+1|2^{k+1}+2-2(k+1)$, which is a contradiction.

For the small computation, first take $i$ up to $\dfrac k2$. By symmetry, it is sufficient. Then, the number of $p$ in denominator is less than that in numerator. It's quite intuitive but I recommend you to draw a line with $p$ multiples points.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.