Prime Factorization – The fundamental theorem of arithmetic

The fundamental theorem of arithmatic states that any number greater than $1$ can be represented as a product of primes and this form of represenation is unique. Now we’ll see two proofs which’ll provide you the intuition why this works. Every integer $n, n \gt 1$ is divisible by at least a prime. If $n$ is a prime, then the l…

Sieve of Eratosthenes – Generate prime numbers

In the last article about prime numbers, I discussed about different types of primilarity test and Trial division method to verify if a number is a prime. If you haven’t read that yet, here is the article, Prime numbers and basic primilarity test. In this article, we’ll focus on sieve of eratosthenes, which helps us to com…

Prime numbers and basic primilarity test

A prime number is a integer greater than $1$ and has no positive divisors other than $1$ and itself. $1$ is neither prime nor composite. The set of positive integers can be divided into three classes, primes, composites and a unit ($1$). For example, $5$ is prime because the only ways of writing it as a product, $1 × 5$ or $5 × 1$, involve $5$…

GCD and Euclidean Algorithm

Suppose we have two integers $a$ and $b$. We say that the number $d$ is the greatest common divisor of $a$ and $b$ if and only if, $d | a$ and $d | b$ and if $c | a$ and $c | b$, then $c \leq d$. Condition $1$ says that $d$ is a common divisor of $a$ and $b$, and condition $2$ says that it is the greatest such divisor. Note that if $a$ and $b$ are not both z…