English
中文
Deutsch
Română
TürkçeDivisibility and PrimesGreatest Common Factors
An architect is planning the floor for a large courtyard that measures 18m by 30m. She wants it to be covered in quadratic tiles, without any gaps or overlaps along the sides. What is the largest size of squares she can use?
The tiles have a size of
Just like before, this question is not about geometry - it is about divisibility. The length of the sides of the tiles has to divide both 18 and 30, and the largest possible number with that property is
Once again, we can use the
18 | = | 2 | × | 3 | × | 3 | ||
30 | = | 2 | × | 3 | × | 5 | ||
Suppose that X is the gcf of 18 and 30. Then X divides 18 so the prime factors of X must be among 2, 3 and 3. Also, X divides 30 so the prime factors of X must be among 2, 3 and 5.
To find X, we simply need to multiply all numbers which are prime factors of
X = 2 × 3 = 6.
Now we have a simple method for finding the gcf of two numbers:
- Find the prime factorisation of each number.
- Multiply the prime factors which are in both numbers.
Once again prime numbers are special: the gcf of two different primes is always
Cryptography
One of the most important modern applications of prime numbers is in a field of mathematics called Cryptography. For thousands of years, people have tried to conceal messages so that only the intended recipient could read them – this is called encryption. It is used by everyone from generals exchanging secret orders during wars to personal emails or online banking details.
People always tried to come up with better, more secure encryption methods, but after some time, they were all broken using yet more advanced algorithms. In the Second World War, the German army used the Enigma: a complex machine consisting of a keyboard, rotating wheels and plugs. It encrypted messages using one of 158 million million million possibilities (that’s a 158 followed by 18 zeros!). The code was widely believed to be unbreakable, but the British Secret Service, led by mathematician Alan Turing, built some of the first computers that managed to decode it.
German four-rotor Enigma machine
Today’s computers are much more advanced, capable of trying millions of possibilities every second. To develop better encryption algorithms, you have to find a mathematical operation that is difficult even for powerful computers. Computers are incredibly fast at addition, subtraction, multiplication and division. However, as it turns out, computers are very slow at factorising large integers into primes…
COMING SOON – RSA example with Alice and Bob
This encryption algorithm is called RSA Cryptography, after its three inventors, Ron Rivest, Adi Shamir and Leonard Adleman who published it in 1977. It turns out that a very similar method was known to the British Secret Service since 1973, but remained classified until much later.
Today, prime numbers are used by computers all over the world to exchange data. As you browse the internet or send chat messages, your phone or laptop will quietly generate large prime numbers and exchange public keys with other computers.