WEBVTT

00:00:02.011 --> 00:00:05.150
Euler continued to investigate the properties of numbers –

00:00:05.150 --> 00:00:09.007
specifically the distribution of prime numbers.

00:00:09.007 --> 00:00:10.919
One important function he defined

00:00:10.919 --> 00:00:12.733
is called the 'phi function.'

00:00:12.733 --> 00:00:15.885
It measures the breakability of a number.

00:00:15.885 --> 00:00:17.879
So, given a number, say, 'n,'

00:00:17.879 --> 00:00:21.439
it outputs how many integers are less than or equal to n

00:00:21.439 --> 00:00:24.921
that do not share any common factors with n.

00:00:24.921 --> 00:00:28.375
For example, if we want to find the phi of 8,

00:00:28.375 --> 00:00:30.868
we look at all values from 1 to 8,

00:00:30.883 --> 00:00:32.983
and then we count how many integers

00:00:32.983 --> 00:00:35.954
8 does not share a factor greater than 1 with.

00:00:35.954 --> 00:00:37.371
Notice, 6 is not counted,

00:00:37.371 --> 00:00:39.302
because 6 and 8 share the factor 2,

00:00:39.302 --> 00:00:42.002
while 1, 3, 5 and 7 are all counted,

00:00:42.002 --> 00:00:44.528
because they only share the factor 1.

00:00:44.528 --> 00:00:48.855
Therefore, phi(8) = 4.

00:00:48.855 --> 00:00:50.271
What's interesting is that

00:00:50.271 --> 00:00:54.523
calculating the Phi function is hard, except in one case.

00:00:54.523 --> 00:00:56.061
Look at this graph.

00:00:56.061 --> 00:01:01.307
It is a plot of values of phi over integers from 1 to 1000.

00:01:01.307 --> 00:01:04.891
Now, notice any predictable pattern?

00:01:04.891 --> 00:01:07.749
The straight line of points along the top

00:01:07.749 --> 00:01:11.016
represents all the prime numbers.

00:01:11.016 --> 00:01:14.463
Since prime numbers have no factors greater than 1,

00:01:14.463 --> 00:01:19.991
the phi of any prime number, 'p,' is simply p-1.

00:01:19.991 --> 00:01:22.616
To calculate phi of 7 – a prime number –

00:01:22.616 --> 00:01:24.984
we count all integers except 7 –

00:01:24.984 --> 00:01:27.575
since none of them share a factor with 7.

00:01:27.575 --> 00:01:31.536
Phi of 7 = 6.

00:01:31.536 --> 00:01:37.905
So if you are asked to find phi of 21,377, a prime number,

00:01:37.905 --> 00:01:41.356
you would only need to subtract 1 to get the solution –

00:01:41.356 --> 00:01:44.132
21,376.

00:01:44.132 --> 00:01:48.090
phi of any prime is easy to compute.

00:01:48.090 --> 00:01:50.766
This leads to an interesting result, based on the fact that

00:01:50.766 --> 00:01:53.875
the phi function is also 'multiplicative.'

00:01:53.875 --> 00:02:00.899
That is, phi(A x B)=phi(A) x Phi(B).

00:02:00.899 --> 00:02:02.792
If we know some number, N,

00:02:02.792 --> 00:02:06.666
is the product of two primes, P1 and P2,

00:02:06.666 --> 00:02:09.627
then phi of N is just the value of

00:02:09.627 --> 00:02:13.434
phi for each prime multiplied together, –

00:02:13.434 --> 00:02:17.057
or (P1 - 1) x (P2 - 1).