b^(n-1)=-1 mod n

Question

By Fermat's little theorem we know that

$$b^{p-1}=1 \mod p$$

if p is prime and $\gcd(b,p)=1$. On the other hand, I was wondering whether

$$b^{n-1}=-1 \mod n$$

can occur at all?

Update: sorry, I meant n odd. Please excuse.

Answer 1

There are no solutions to $b^{n-1}\equiv-1\pmod n$ with $n$ odd.

Let $n>1$ be odd. Every prime dividing $n$ can be written as $2^km+1$ for some positive $k$ and some odd integer $m$. Among those primes, let $p$ have the minimal value of $k$. Then $n-1=2^kr$ for some integer $r$. If $b^{n-1}\equiv-1\pmod n$ then $b^{n-1}\equiv-1\pmod p$ so $b^{(n-1)m}\equiv(-1)^m\equiv-1\pmod p$ and $\gcd(b,p)=1$. But $b^{(n-1)m}=b^{2^kmr}=b^{(p-1)r}\equiv1\pmod p$ by little Fermat. Contradiction, QED.

Answer 2

It's clear that b = n-1 with n even gives a solution. But there are many other solutions. Here are the solutions $(b,n)$ not of the form $(2k-1, 2k)$, with n less than or equal to 200, from MAPLE.

L := []: for n from 2 to 200 do 
for b from 1 to n-2 do 
if (b^(n-1) mod n) = n-1 then L := [op(L), [b,n]]; fi:
od: od:
L;
[[3, 28], [19, 28], [23, 52], [43, 52], [17, 66], [29, 66], [35, 66],
[41, 66], [19, 70], [59, 70], [27, 76], [31, 76], [31, 112], [47, 112], 
[99, 124], [119, 124], [49, 130], [69, 130], [11, 148], [27, 148], [87, 154], 
[131, 154], [7, 172], [123, 172], [63, 176], [79, 176], [95, 176], [127, 176],
[23, 186], [29, 186], [77, 186], [89, 186], [29, 190], [59, 190], [69, 190], 
[79, 190], [89, 190], [109, 190], [129, 190], [179, 190], [19, 196], [31, 196]]

For example, $3^{28-1} \equiv -1 \mod 28$, so the pair [3,28] is on the list.

I can't make sense of this output myself, but maybe someone else can?

Answer 3

That would be equivalent to $2(n-1) = k\varphi(n)$ and $n-1\ne k'\varphi(n)$ by Fermat's little theorem for composite numbers.

The second condition is equivalent to being able to satisfy first with $k$ odd, so we could try $k = 3$. Thus we have $n = 3n' +1$ and $2n' = \varphi(3n' + 1)$. Now the trivial choice for $n' =1$ works!

Thus we find $n = 4$: $$(-1)^{(4-1)} = -1 (\mathop{\text{mod}} 4).$$

Answer 4

This is something that brute force can answer:

In[1]:= Reap[Do[
   If[Mod[PowerMod[a, n - 1, n] + 1 , n] == 0, Sow[{a, n}]],
   {n, 2, 20},
   {a, 1, n - 1}
   ]][[2, 1]]

Out[1]= {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {13, 14}, 
         {15, 16}, {17, 18}, {19, 20}}

(This lists the pairs $(b,n)$ for $n$ at most 20)

Answer 5

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.