Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

4 Answers

up vote 10 down vote accepted

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.

share|improve this answer
    
Thanks, that looks great! –  Martin Rubey Mar 16 '10 at 22:03
add comment

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?

share|improve this answer
6  
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
add comment

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

share|improve this answer
    
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
add comment

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)

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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