An integer p > 1 is prime if it has no positive divisors other than 1 and itself. No even number, except 2, is prime. Because 2 additional information There are infinitely many primes Credit: Euler. Proof: Assume to the contrary that there are finitely many primes. p_1, …, p_{n}. We desire to make a new prime to reach contradiction. Consider:

Note that p_1 \times … \times p_{n} is divisible by each of the p_{j}. If some p_i |N, p_{i}|1, which is impossible as 1 is not divisible by anything. So, no p_{i} divides N. If N is now prime, we are done as it is not in the list of p_{j}. If not, pick any prime divisor p of N. We will note that given no p_{j} divides N, therefore any prime divisor is a new prime. Having made a new prime, we reach contradiction. \blacksquare coprime Two integers a, b is considered coprime if \gcd (a,b) = 1. Therefore, because greatest common divisor is a linear combination