Prime numbers are like atoms – they are the building blocks of integers. A prime is any natural number having exactly 2 positive divisors – 1 and itself. $\\$

One of the most important theorems of mathematics, so important, that it is called the fundamental theorem of arithmetic, is about primes. It says that every natural number can be decomposed into a product of primes in exactly one way (up to a rearrangement). Today, we will explore some of the consequences of that theorem. $\\$ Firstly, a prime decomposition of a product of two numbers is a product of the decompositions of these numbers, and so contains all the primes that appear in both decompositions. Secondly, a number is divisible by another number if and only if all the primes in the decomposition of the divisor also appear in the decomposition of the dividend. We can think about dividing natural number as a smaller number “stealing” some of the prime divisors of the larger number. We will see how this simple fact can help us answer some questions about divisibility.

Problems:

a) The number $a$ is not divisible by $3$. Could the number $2a$ be divisible by $3$? $\\$ b) We know that the product $c \times d$ is divisible by a prime $p$. Show that either $c$ or $d$ must be divisible by $p$.

Find a number which: $\\$

a) It is divisible by $4$ and by $6$, is has a total of 3 prime factors, which may be repeated. $\\$

b) It is divisible by $6, 9$ and $4$, but not divisible by $27$. It has $4$ prime factors in total, which may be repeated. $\\$

c) It is divisible by $5$ and has exactly $3$ positive divisors.

a) The number $a$ has a prime factorization $2^3 \times 3^2 \times 7^2 \times 11$. Is it divisible by $54$? Is it divisible by $154$? $\\$ b) The prime factorization of the number $b$ is $2 \times 5^2 \times 7 \times 13^2 \times 17$. The prime factorization of the number $c$ is $2^2 \times 5 \times 7^2 \times 13$. Is the first number divisible by the second one? Is the product of these two numbers, $b \times c$, divisible by $49000$? $\\$

a) The number $a$ is even. Should $3a$ definitely also be even? $\\$ b) The number $5c$ is divisible by $3$. Is it true that $c$ is definitely divisible by $3$? $\\$ c) The product $a \times b$ is divisible by $7$. Is it true that one of these numbers is divisible by $7$? $\\$ d) The product $c \times d$ is divisible by $26$. Is it true that one of these numbers is divisible by $26$?

Look at this formula found by Euler: $n^2 +n +41$. It has a remarkable property: for every integer number from $1$ to $21$ it always produces prime numbers. For example, for $n=3$ it is $53$, a prime. For $n=20$ it is $461$, also a prime, and for $n=21$ it is $503$, prime as well. Could it be that thiss formula produces a prime number for any natural $n$?