1
$\begingroup$

Possible Duplicate:
Accuracy of Fermat's Little Theorem?

$n$ is odd and composite number,and there exists $b_0$ , $0 such that $gcd(n,b_0)=1$ and ${b_0}^{n-1} \not \equiv {1} \mod{n}$

prove that there are at least 50% of numbers $b$ such that $0 and $gcd(b,n)=1$ which satisfy ${b_0}^{n-1} \not \equiv {1} \mod{n}$

  • 0
    (Note that the assumption that $n$ is composite is redundant, since $b_0^{n-1}\equiv1\bmod n$ for $n$ prime by Fermat's little theorem.)2012-07-25

0 Answers 0