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

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.

-
Yes. $n=2$ and $b$ odd. –  Theo Johnson-Freyd Jan 10 '10 at 0:07
Which is to say: a better question is "for what $b,n$ is...", which is closer to the answers given below. –  Theo Johnson-Freyd Jan 10 '10 at 0:09

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.

-
Thanks, that looks great! –  Martin Rubey Mar 16 '10 at 22:03

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?

-
The $n$'s show up in research.att.com/~njas/sequences/A039772 –  Mariano Suárez-Alvarez Jan 9 '10 at 22:02
@Michael - Would you mind calculating [b,n] with a slightly larger range for n (i.e. up to 500 or 1000; I would do this myself but don't have access to a computer algebra system right now)? I'm just curious as to whether or not any solutions pop up with n odd. –  Ben Linowitz Jan 10 '10 at 16:16
There are no solutions with $n \le 4119$ and $n$ odd. (There's nothing special about this number; I just got tired of waiting.) –  Michael Lugo Jan 10 '10 at 17:33

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).$$

-
I think you've actually used the converse to Fermat's little theorem here, which is not actually true! (It comes pretty close to being true, though, in the sense that there are few counterexamples.) –  Michael Lugo Jan 9 '10 at 21:44
I agree I answered a slightly different question, namely whether the equality is true for $b$ being a primitive root. –  Ilya Nikokoshev Jan 10 '10 at 0:01

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)

-
Hm, it's obvious that (2k-1,2k) gives a family of silutions, so the only questions remains - are there another solutions? –  Nurdin Takenov Jan 9 '10 at 21:34
Nurdin, there are other solutions if you take the brute force a bit further; the first one is at n = 28. See my answer above. –  Michael Lugo Jan 9 '10 at 21:56