Euler, Fermat and Primality Test
In number theory, The Euler’s totient function, counts the number of positive integers less than m and relatively prime to m. For a prime number p, φ(p) = p-1.
It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1.
What is Fermat’s little theorem
Fermat’s little theorem says that if p is a prime and a is not a multiple of p, then
Euler’s generalization of Fermat’s little theorem says that if a is relatively prime to m, then
Euler’s totient function is multiplicative, that is, if a and b are relatively prime, then φ(ab) = φ(a) φ(b). We will use this fact in other discuss.
The Proof of generalization
Be r=φ(n) and b₀, b₁, …, bᵣ, integers numbers, primes relative two at two, and all prime relative with n. So ab₀, ab₁, …, abᵣ, still congruent mod(n) for
i=1,2, …,r.
The collection b₀, b₁, …, bᵣ and ab₀, ab₁, …, abᵣ are equals mod(n). So let multiplity all
So,
In anyway, (aʳ-1) ≡ 0 (mod n) and how aʳ ≡ 1(mod n) and
r=φ(n), then
Primality testing
One best things about this theorem is the primality testing.
The contrapositive of Fermat’s little theorem is useful: if the congruence aᵖ⁻¹≡ 1 (mod p) does not true, then either p is not prime or a is a multiple of p. In practice, a is much smaller than p, and so one can conclude that p is not prime.
Technically this is a test for non-primality: it can only prove that a number is not prime. For example, if 2ᵖ⁻¹ ≢ 1 (mod p) then we know p is not a prime. But if 2ᵖ⁻¹ ≡ 1 (mod p) then all we know is that we haven’t failed the test; we don’t have certain if that p is prime or not. So we try another value of a, for example 5, and see if 5ᵖ⁻¹ ≡ 1 (mod p).
In theory looks perfect, so all the crypto theory was ruined? Of course, not, because even easy to undestand, looking in thecomputacionais terms, this is problematic, for example, for a small number like 223, and for a with value of 2, we have;
We know that 223 is prime, but 2²²³ is hard to compute even in robusts computers, so numbers like 2321412341243123423413263466567678352323 is harder to determine, but all the theory is usefull, with many implications in criptography and number theory. I will discuss this in other posts.
