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, ifaandbare 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.

## Top comments (0)