b^(n-1)=-1 mod n - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T07:25:49Z http://mathoverflow.net/feeds/question/11249 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11249/bn-1-1-mod-n b^(n-1)=-1 mod n Martin Rubey 2010-01-09T20:47:23Z 2011-10-31T04:09:58Z <p>By Fermat's little theorem we know that</p> <p>$$b^{p-1}=1 \mod p$$</p> <p>if p is prime and $\gcd(b,p)=1$. On the other hand, I was wondering whether</p> <p>$$b^{n-1}=-1 \mod n$$</p> <p>can occur at all?</p> <p>Update: sorry, I meant n odd. Please excuse.</p> http://mathoverflow.net/questions/11249/bn-1-1-mod-n/11250#11250 Answer by Ilya Nikokoshev for b^(n-1)=-1 mod n Ilya Nikokoshev 2010-01-09T20:59:54Z 2010-01-09T20:59:54Z <p>That would be equivalent to $2(n-1) = k\varphi(n)$ and $n-1\ne k'\varphi(n)$ by <a href="http://en.wikipedia.org/wiki/Fermat%27s%5Flittle%5Ftheorem" rel="nofollow">Fermat's little theorem for composite numbers</a>. </p> <p>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!</p> <p>Thus we find $n = 4$: $$(-1)^{(4-1)} = -1 (\mathop{\text{mod}} 4).$$</p> http://mathoverflow.net/questions/11249/bn-1-1-mod-n/11251#11251 Answer by Mariano Suárez-Alvarez for b^(n-1)=-1 mod n Mariano Suárez-Alvarez 2010-01-09T21:08:12Z 2010-01-09T21:08:12Z <p>This is something that brute force can answer:</p> <pre> 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}} </pre> <p>(This lists the pairs $(b,n)$ for $n$ at most 20)</p> http://mathoverflow.net/questions/11249/bn-1-1-mod-n/11258#11258 Answer by Michael Lugo for b^(n-1)=-1 mod n Michael Lugo 2010-01-09T21:55:25Z 2010-01-09T21:55:25Z <p>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)$ <i>not</i> of the form $(2k-1, 2k)$, with n less than or equal to 200, from MAPLE.</p> <pre><code>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]] </code></pre> <p>For example, $3^{28-1} \equiv -1 \mod 28$, so the pair [3,28] is on the list.</p> <p>I can't make sense of this output myself, but maybe someone else can?</p> http://mathoverflow.net/questions/11249/bn-1-1-mod-n/18428#18428 Answer by Gerry Myerson for b^(n-1)=-1 mod n Gerry Myerson 2010-03-16T21:31:37Z 2010-03-16T21:31:37Z <p>There are no solutions to $b^{n-1}\equiv-1\pmod n$ with $n$ odd. </p> <p>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. </p>