Fermat Quotient

Author

Eric W. Weisstein
August 10, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/FermatQuotient.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/FermatQuotient.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Code

FermatQuotient[p_, a_] := Mod[(a^(p - 1) - 1)/p, p]

SetAttributes[MyMod,Listable];
MyMod[r_Rational,m_Integer]:=Mod[Numerator[r]PowerMod[Denominator[r],-1,m],m]
MyMod[i_,m_]:=Mod[i,m]

Enumeration

(1/2) (∑_(k=1)^(p-1))((((-1))^(k-1))/k)

V6

(1/2)Sum[((((-1))^(k-1))/k),{k,p-1}]

FullSimplify[%]

V7

(1/2)Sum[((((-1))^(k-1))/k),{k,p-1}]

FullSimplify[%]

FullSimplify[%-(1/4) (Log[4]+(((-1))^p) (-PolyGamma[0,(p/2)]+PolyGamma[0,((1+p)/2)]))]

(1/2) (∑_(k=((p+1)/2))^(p-1))(1/k)

V6

FullSimplify[(1/2)Sum[(1/k),{k,(p+1)/2,p-1}]]

V7

(1/2)Sum[(1/k),{k,(p+1)/2,p-1}]

Simplify[%]

Comparison

Function[p,{
(1/4) (Log[4]+(((-1))^p) (-PolyGamma[0,(p/2)]+PolyGamma[0,((1+p)/2)])),
(1/2) (PolyGamma[0,p]-PolyGamma[0,((1+p)/2)])
}//FullSimplify]/@Prime[Range[10]]

Function[p,MyMod[{
(1/4) (Log[4]+(((-1))^p) (-PolyGamma[0,(p/2)]+PolyGamma[0,((1+p)/2)])),
(1/2) (PolyGamma[0,p]-PolyGamma[0,((1+p)/2)]),
FermatQuotient[p,2]
}//FullSimplify,p]]/@Prime[Range[2,10]]

FermatQuotient[#,2]&/@Prime[Range[2,20]]

l=Flatten[Position[Sqrt[FermatQuotient[#, 2]]&/@Prime[Range[100]],_Integer,{1}]]

Prime/@l

Select[Table[Prime[n], {n, 1, 1000}], (FermatQuotient[#, 2] == 0) &]

Prime/@Position[FermatQuotient[#,2]&/@Prime[Range[10^4]],0]//Flatten//Timing