Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
dromniscience
dromniscience
  • 111
  • 3

Another proof of no solution to $b^{n-1}\equiv-1\pmod{n}$ with $n$ odd. It is based on a neat lemma.

Lemma. Let $p>2$ be a prime. Then $x^{2^t}\equiv-1\pmod{p}$ has a solution iff $n\equiv1\pmod{2^{t+1}}$$p\equiv1\pmod{2^{t+1}}$.

Sketch of the proof. Prove by induction. The base case where $t=0$ is trivial. Suppose we have proved for $t=t_0$ and we consider $t=t_0+1$.

  • Necessity: Suppose $\left({x_0}^2\right)^{2^{t_0}}\equiv{x_0}^{2^{t_0+1}}\equiv-1\pmod p$. Let $x_0^2\equiv a\pmod{p}$ and $a$ must be a quadratic residual of $p$. Hence, $a^{\frac{p-1}2}\equiv1\pmod p$. Noting that $a^{2^{t_0}}\equiv-1\pmod p$ and $2^{t_0}|\frac{p-1}2$ (from the inductive assumption), there must be $2^{t_0+1}|\frac{p-1}2$ and thus the result.
  • Sufficiency: From the assumption we know $x^{2^{t_0}}\equiv-1\pmod{p}$ has a solution $x_0$. Moreover, since ${x_0}^\frac{p-1}2\equiv\left({x_0}^{2^{t_0+1}}\right)^{\frac{p-1}{2^{t_0+2}}}\equiv1\pmod{p}$, $x_0$ is a quadratic residual, which concludes the induction step.

Back to the problem: Prove by contradiction.

If not, let $2^t\|n-1$ where $t>0$. For any prime $p|n$, we have $2^{t+1}|p-1$ since $\left(b^{\frac{n-1}{2^t}}\right)^{2^t}\equiv-1\pmod{p}$ has a solution. However, this fact implies $2^{t+1}|n-1$, which is a contradiction. Hence, there is no such solution $(b,n)$ with $n$ odd.

Another proof of no solution to $b^{n-1}\equiv-1\pmod{n}$ with $n$ odd. It is based on a neat lemma.

Lemma. Let $p>2$ be a prime. Then $x^{2^t}\equiv-1\pmod{p}$ has a solution iff $n\equiv1\pmod{2^{t+1}}$.

Sketch of the proof. Prove by induction. The base case where $t=0$ is trivial. Suppose we have proved for $t=t_0$ and we consider $t=t_0+1$.

  • Necessity: Suppose $\left({x_0}^2\right)^{2^{t_0}}\equiv{x_0}^{2^{t_0+1}}\equiv-1\pmod p$. Let $x_0^2\equiv a\pmod{p}$ and $a$ must be a quadratic residual of $p$. Hence, $a^{\frac{p-1}2}\equiv1\pmod p$. Noting that $a^{2^{t_0}}\equiv-1\pmod p$ and $2^{t_0}|\frac{p-1}2$ (from the inductive assumption), there must be $2^{t_0+1}|\frac{p-1}2$ and thus the result.
  • Sufficiency: From the assumption we know $x^{2^{t_0}}\equiv-1\pmod{p}$ has a solution $x_0$. Moreover, since ${x_0}^\frac{p-1}2\equiv\left({x_0}^{2^{t_0+1}}\right)^{\frac{p-1}{2^{t_0+2}}}\equiv1\pmod{p}$, $x_0$ is a quadratic residual, which concludes the induction step.

Back to the problem: Prove by contradiction.

If not, let $2^t\|n-1$ where $t>0$. For any prime $p|n$, we have $2^{t+1}|p-1$ since $\left(b^{\frac{n-1}{2^t}}\right)^{2^t}\equiv-1\pmod{p}$ has a solution. However, this fact implies $2^{t+1}|n-1$, which is a contradiction. Hence, there is no such solution $(b,n)$ with $n$ odd.

Another proof of no solution to $b^{n-1}\equiv-1\pmod{n}$ with $n$ odd. It is based on a neat lemma.

Lemma. Let $p>2$ be a prime. Then $x^{2^t}\equiv-1\pmod{p}$ has a solution iff $p\equiv1\pmod{2^{t+1}}$.

Sketch of the proof. Prove by induction. The base case where $t=0$ is trivial. Suppose we have proved for $t=t_0$ and we consider $t=t_0+1$.

  • Necessity: Suppose $\left({x_0}^2\right)^{2^{t_0}}\equiv{x_0}^{2^{t_0+1}}\equiv-1\pmod p$. Let $x_0^2\equiv a\pmod{p}$ and $a$ must be a quadratic residual of $p$. Hence, $a^{\frac{p-1}2}\equiv1\pmod p$. Noting that $a^{2^{t_0}}\equiv-1\pmod p$ and $2^{t_0}|\frac{p-1}2$ (from the inductive assumption), there must be $2^{t_0+1}|\frac{p-1}2$ and thus the result.
  • Sufficiency: From the assumption we know $x^{2^{t_0}}\equiv-1\pmod{p}$ has a solution $x_0$. Moreover, since ${x_0}^\frac{p-1}2\equiv\left({x_0}^{2^{t_0+1}}\right)^{\frac{p-1}{2^{t_0+2}}}\equiv1\pmod{p}$, $x_0$ is a quadratic residual, which concludes the induction step.

Back to the problem: Prove by contradiction.

If not, let $2^t\|n-1$ where $t>0$. For any prime $p|n$, we have $2^{t+1}|p-1$ since $\left(b^{\frac{n-1}{2^t}}\right)^{2^t}\equiv-1\pmod{p}$ has a solution. However, this fact implies $2^{t+1}|n-1$, which is a contradiction. Hence, there is no such solution $(b,n)$ with $n$ odd.

Source Link
dromniscience
dromniscience
  • 111
  • 3

Another proof of no solution to $b^{n-1}\equiv-1\pmod{n}$ with $n$ odd. It is based on a neat lemma.

Lemma. Let $p>2$ be a prime. Then $x^{2^t}\equiv-1\pmod{p}$ has a solution iff $n\equiv1\pmod{2^{t+1}}$.

Sketch of the proof. Prove by induction. The base case where $t=0$ is trivial. Suppose we have proved for $t=t_0$ and we consider $t=t_0+1$.

  • Necessity: Suppose $\left({x_0}^2\right)^{2^{t_0}}\equiv{x_0}^{2^{t_0+1}}\equiv-1\pmod p$. Let $x_0^2\equiv a\pmod{p}$ and $a$ must be a quadratic residual of $p$. Hence, $a^{\frac{p-1}2}\equiv1\pmod p$. Noting that $a^{2^{t_0}}\equiv-1\pmod p$ and $2^{t_0}|\frac{p-1}2$ (from the inductive assumption), there must be $2^{t_0+1}|\frac{p-1}2$ and thus the result.
  • Sufficiency: From the assumption we know $x^{2^{t_0}}\equiv-1\pmod{p}$ has a solution $x_0$. Moreover, since ${x_0}^\frac{p-1}2\equiv\left({x_0}^{2^{t_0+1}}\right)^{\frac{p-1}{2^{t_0+2}}}\equiv1\pmod{p}$, $x_0$ is a quadratic residual, which concludes the induction step.

Back to the problem: Prove by contradiction.

If not, let $2^t\|n-1$ where $t>0$. For any prime $p|n$, we have $2^{t+1}|p-1$ since $\left(b^{\frac{n-1}{2^t}}\right)^{2^t}\equiv-1\pmod{p}$ has a solution. However, this fact implies $2^{t+1}|n-1$, which is a contradiction. Hence, there is no such solution $(b,n)$ with $n$ odd.