## DEV Community

Pedro Matias de Araujo

Posted on • Originally published at Medium on

# 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 