Welcome to NRICH.

 
Euler's phi function
By Irfan on Friday, March 19, 1999 - 01:47 pm:

I have been given a problem that is to find the phi of a three or four figure number. How do I do this? Also, are there any patterns in the phi function?

Irfan

By The Editor:

This thread originally arose because this problem was set as a GCSE coursework. If you are reading this because you are doing a coursework, please remember that you are required to declare any help you have got outside the classroom. This does not necessarily affect your mark, particularly as we try not to give more than hints. However you may decide not to read any more if you think you can get further without any help.

By Alex Barnard (Agb21) on Friday, March 19, 1999 - 01:58 pm:

Irfan,

phi(x) is defined to be the number of positive numbers less than x which are coprime to x.

So the silly way to calculate phi is to just do exactly that... go through all the numbers less than x and see which ones are coprime to it. This is fine if x is very small. With a computer you could do up to 6 or 7 digits without much problem. So the first thing you should do is to work out phi(x) for as long as you can be bothered (at least to x=30).

Do you see any patterns?

As this is about divisibility it is often good to look at primes.

What is phi of a prime?

What about phi of the square of a prime?

Etc...

What about the product of two different primes?

Etc...

Hopefully you will have spotted some patterns by the time you've looked at the above special cases.

A multiplicative function is a function f such that f(a × b) = f(a) × f(b). Is phi multiplicative? [Hint : NO]. Is it ALMOST multiplicative? [Hint : YES]. Where and how does it go wrong?

If you got this far then you probably have worked out the properties that phi has and you will be able to do your question.

Write back if you want any more clues or answers...

AlexB.

By KATH on Friday, March 19, 1999 - 08:45 pm:

I have been asked to find the phi function of 19600 without writing down all its factors. Is there a rule?
KATH

By Alex Barnard (Agb21) on Monday, March 22, 1999 - 11:33 am:

YES

There are enough clues in the above reply to allow you to work out roughly what the rules the phi function obeys.

Work out phi of 2,4,8,16,32,...
and then phi of 3,9,27,81,...

You should see a pattern in these which might allow you to guess what phi of 5,25,125,... is.

Now work out phi of 2×3,2×5,2×7,2×9,...
and then phi of 3×5, 3×7, 3×11, ...

Compare the answers you get to phi of the factors - ie. compare phi(3×7) to phi(3) and phi(7). You will see a pattern here too.

If you spot both these patterns then you will be able to work out phi of any number (including 19600).

Sorry if you think I'm being awkward by not directly answering your question but it seems like a slightly strange question to ask us. If you've been asked to work out phi of 19600 and not been told any rules then you've not got a chance without a computer. So it seems that you are meant to find the rule for yourself... I'm not going to spoil your fun looking for it but there are enough clues here to help you on your way.

By The Editor:

The following posts are from a separate thread about Euler's phi function. The reply gives rather more information than will be helpful if you are doing GCSE coursework, so if that's you, stop reading here!

By David Ball on February 18, 1998:

1. How do I obtain f(n) for 5 different values of `n'.

2. Why is the following equation only sometimes true:

f(n×m) = f(n) × f(m)


Thankyou for the help.

David Ball

By Anonymous on Monday, September 11, 2000 - 02:56 pm:

You can work out for yourself that f(2)=1, f(3)=2, f(4)=2, f(5)=4, f(6)=2, f(7)=6, f(8)=4, f(9)=6 etc.

Looking at the statement f(n×m) = f(n)×f(m) we see that

f(6) = f(2)*f(3)

f(12) = f(3)*f(4)

but f(9) ¹ f(3)*f(3)

and f(12) ¹ f(2)*f(6).

In fact the statememnt is true if and only if m and n are coprime.

The proof is as follows.

Draw an array with 1, ... , m in the first row

m+1, ... , 2m in the second row etc.

and (n-1)m, ... , nm in the last row.

(You might like to do this for m=4 and n=3 as an example.)


We colour a number red if it is coprime with m and blue if it is coprime with n. The colour will be purple if the number is coprime with m and also with n, equivalently coprime with mn.

There will be f(m) red columns. Why does this always happen? The reason is that when you divide the numbers in the row by m, each row contains the remainders 1, 2, ..., (m-1),0 in this order, so you get f(m) red columns. (What we are talking about here is really modulus arithmetic.)

If m and n are coprime each column will contain exactly f(n) blue numbers so there will be f(m)*f(n) coloured purple. Again this happens because when you divide the numbers by n you see that each column contains all the possible remainders. These remainders however do not occur in the same order in each column so we will not get entirely blue rows.

If m and n are not coprime then the number of blue numbers in a column will not be f(n) so the result is not true.

If you write out and colour arrays of numbers for different values of m and n you will soon see what is going on.

You might like to go a bit further to see how this result can be used, for any number n whatsoever, to get f(n) by splitting n into a product of prime factors.

Best wishes

By The Editor:

For lots more about Euler's phi function, see here.