Euler, Fermat and Primality Test
Tags: primenumbers, cryptography, mathematics
Published: 2019-04-03 03:09:39

---
title: Euler, Fermat and Primality Test
published: true
tags: prime-numbers,cryptography,mathematics
canonical_url: 
---

![](https://cdn-images-1.medium.com/max/800/1*gyD2i1OZWaKSDWB6rj8nFw.jpeg)

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**](https://en.wikipedia.org/wiki/Fermat's_little_theorem) says that if _p_ is a prime and _a_ is not a multiple of _p_, then

![](https://cdn-images-1.medium.com/max/173/1*CotGjw6Dd51xqzfvJvSNFA.jpeg)

**Euler’s generalization** of Fermat’s little theorem says that if _a_ is relatively prime to _m_, then

![](https://cdn-images-1.medium.com/max/225/1*BPy80qeKAXp309Edp0qolA.jpeg)

> 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

![](https://cdn-images-1.medium.com/max/279/1*2nRFSnPCtON2oJT0g7jawQ.png)

So,

![](https://cdn-images-1.medium.com/max/493/1*R5O59TzgeqQVCMkcx2roAQ.png)

In anyway, _(aʳ-1) ≡ 0 (mod n)_ and how _aʳ ≡ 1(mod n)_ and  
_r=φ(n)_, then

![](https://cdn-images-1.medium.com/max/255/1*Ok_DVBZh52E-ES2yp3AOgQ.png)

### 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;

![](https://cdn-images-1.medium.com/max/406/1*l1R6OLprvEaE8bu_C-Ulrw.png)

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.