4
$\begingroup$

I am little bit confused with the definition of Carmichael Number

Wikipedia(http://en.wikipedia.org/wiki/Carmichael_number) saying that

Carmichael Number is a composite number satisfies

$b^{n}\equiv b \mod {n}$

for all integers $1<b<n$

Wolfram Mathworld(http://mathworld.wolfram.com/CarmichaelNumber.html) says that

Carmichael Number is a composite number satisfies

$a^{n-1}\equiv 1\mod {n}$

for all integers $1<a<n$

Which one of the above is correct ?

Doubt arosed because if $b^{n}\equiv b \mod {n}$ and if $b$ is not divisible by $n$ then its not necessary that $b^{n-1}\equiv b\mod {n}$

example : $3^{561} \equiv3\mod{561} $ but $3^{560}\not \equiv 1 mod{561}$

$\endgroup$
3
$\begingroup$

The first (Wikipedia) answer is the correct one. Actually if you read further into Wolfram Mathworld link it says : "Carmichael Number is a composite number that satisfies

$$a^{n-1} \equiv 1 \pmod n$$

for every choice of $a$ satisfying $(a,n) = 1$ with $1 < a < n$"

Actually this is true due rules of modular arithmetics, which states that if the left hand and right hand side have common divisor then we can divide them both by it. If the common divisor divides the modulo, we must divide it, otherwise we don't divide it.

$\endgroup$
  • 1
    $\begingroup$ yeah , Thanku . $\endgroup$ – hanugm Feb 2 '14 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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