Definition (Composite number)
A composite number is a natural number, n∈N, that has at least one proper divisor, d, such that 1<d<n.
Definition (Pseudoprime)
A composite number is called a base a pseudoprime if an−1≡1(modn)
Definition (Carmichael number)
If a composite number, n, is pseudoprime ∀a∈N,a<n,(a,n)=1 then it is called a Carmichael Number.
Theorem (1.16)
Let b∈Z,n∈N
- d∣n⟹(bd−1)∣(bn−1)
- \begin{array}
&&(b,m)=1 \\
&b^{a}\equiv 1\pmod{m} \\
&b^{c}\equiv 1\pmod{m}
\end{array}\implies b^{d}\equiv 1\pmod{m} where d=(a,c).
Theorem (1.17)
If d=(a,c) then (ba−1,bc−1)=bd−1
Theorem (1.18)
If p is a prime divisor of bn−1 then either
- p∣(bd−1) for some d∣n or
- p≡1(modn) If p>2 and n odd, then for 2, we have p≡1(mod2n).