function + prime

[scmetzger]

Can anybody explain how I get this answer:

The function f is defined for all positive integers n by the following rule: f(n) is the number of positive integers each of which is less than n and has no positive factor in common with n other than 1. If p is any prime number then f(p)=?

The answer is: p-1


Thanks for your help.

[dtweah]

Can anybody explain how I get this answer:

The function f is defined for all positive integers n by the following rule: f(n) is the number of positive integers each of which is less than n and has no positive factor in common with n other than 1. If p is any prime number then f(p)=?

The answer is: p-1


Thanks for your help.

f(1)=0
f(2)=1
f(3)=2
f(4)=3
....
f(n)=n-1

Hence f(p)=p-1

The point is that the series will alternate between odd and even numbers so the only common factor will be any consecutive terms of the series will be 1. 3 is prime above and gives 3-1=2

[Ian Stewart]

f(n) does not equal n-1 in general here; it's important that the number in the question is prime.

The definition in the question is quite abstract - if you can make sense of it, however, you should have a good chance of answering the question. We're told: "f(n) is the number of positive integers each of which is less than n and has no positive factor in common with n other than 1."

So to first take an example that isn't relevant to the question, let's figure out what f(6) is. We first need to look at all of the positive integers which are less than 6 -- 1, 2, 3, 4 and 5 -- and decide which of these 'has no positive factor in common with 6 other than 1'. So we want to count how many of these numbers do *not* share a divisor larger than 1 with 6 - i.e. how many of these numbers are not divisible by 2, 3 or 6. We can rule out 2, 3 and 4, but not 1 or 5, so f(6) = 2. (you might notice that we're simply counting all the numbers n < 6 for which the GCD of n and 6 is equal to 1).

If, however, you take any prime number, as they ask us to do in this question -- perhaps take p=7 for example -- we then want to count how many of these numbers -- 1, 2, 3, 4, 5, 6 -- do not have a divisor larger than one in common with 7. Of course, all of them do not share such a divisor with 7, because 7 is prime, so f(7) = 6. The same will be true for any prime p; f(p) = p-1.