# Definition(s) > [!NOTE] Definition (Prime) > Suppose $p$ is a [[Natural Numbers|natural number]] greater than one. Then $p$ is *prime* iff it has exactly two positive [[Divisibility in Integers|divisors]]. I.e. for all $x,y\in \mathbb{N}$ such that $p=xy$, $x=1$ or $y=1$. # Properties [[A Prime that Divides a Product of Integers Must Divide At Least On Factor (Euclid's Lemma)|Euclid's lemma]] asserts that if $p\mid ab$ then $p\mid a$ or $p\mid b$. **Infinitude of primes**: [[Infinitude of primes|Euclid's theorem]] asserts that there are infinitely many primes. **Prime testing**: (Necessary conditions) [[Wilson's Theorem|Wilson's theorem]] asserts that for any integer $p>1,$ $(p-1)!\equiv-1 \pmod{p}$ iff $p$ is prime. Also the Chinese remainder theorem gives that $p$ is prime iff $1$ has two [[Quadratic residue|square roots]] modulo $p.$ (Sufficient conditions) [[Fermat's Little Theorem|Fermat's little theorem]] asserts that if $p$ is prime $a^{p-1} \equiv 1 \pmod{p}$ for all integers $a$ that are not divisible by $p.$ Note that are numbers that satisfy Fermat's condition but are not prime known as [[Carmichael Numbers|Carmichael numbers]]. # Applications **Prime factorisation**: The [[Integers form Unique Factorisation Domain (Fundamental Theorem of Arithmetic)|FTA]] asserts that every natural number can be expressed uniquely as a product of primes. **Primality testing algorithms:** is decision problem of deciding whether a given natural number $N$ is prime. A [[Brute Force Prime Test Implementation in Python|brute-force algorithm]] is to try all possible divisors up to $\sqrt{ N }.$ A related algorithm is the [[Sieve of Eratosthenes|Eratosthenes sieve]] which lists all the primes up to $N.$ The [[Fermat Primality Test|Fermat test]]... The [[Miller-Rabin Primality Test|Miller-Rabin test]]... **Cryptography**: [[Diffie-Hellman Key Exchange|Diffie-Hellman]] is an algorithm for key-exchange that uses [[Primitive Root Modulo n|primitive roots]] of $\mathbb{Z}/p\mathbb{Z}$. Both parties use that common key for subsequent data exchange using symmetric key encryption. [[RSA]] is an algorithm for asymmetric key encryption that generates a public-private key pair. **Generalisations**: [[Irreducible Elements of Integral Domain]].