# Basic Algebra? f:Z+ ---> Z*, s.t. f(n)=p/q, p + q = n, 0< p/q < 1 and gcd(p, q) =1

#### Jomo

##### Elite Member
Basic Algebra? f:Z+ ---> Z*, s.t. f(n)=p/q, p + q = n, 0< p/q < 1 and gcd(p, q) =1

Let f:Z+ ---> Z* be the function that assigns to each positive integer n the number of rational numbers p/q such that

p + q = n, 0< p/q < 1 and gcd(p, q) =1

For example, when n=8 we have 2 such rational numbers: 1/7 and 3/5. Hence f(8) = 2.

What is the first positive integer m such that there is no solution to f(n) = m?

#### daon2

##### Full Member
The number of such rationals $$\displaystyle k/(n-k)$$ is

$$\displaystyle \displaystyle \dfrac{1}{2}\sum_{(k,n-k)=1} 1 = \dfrac{1}{2}\sum_{(n,k)=1} 1 = \dfrac{1}{2}\phi(n)$$

Where the 1/2 is for double counting, e.g. 3/5, 5/3, and $$\displaystyle \phi(n)$$, the number of integers between 1 and n that are relatively prime to n, is Euler's function.

If $$\displaystyle n$$ has prime factorization $$\displaystyle p_1^{e_1}\cdots p_k^{e^k}$$, then as $$\displaystyle \phi(\cdot)$$ is multiplicative we have

$$\displaystyle \phi(n) = \phi(p_1^{e_1})\phi(p_2^{e_2})\cdots\phi(p_k^{e_k})$$

It is not hard to see that $$\displaystyle \phi(p^i) = p^{i-1}(p_i-1)$$ and so

$$\displaystyle \displaystyle \phi(n) = \prod p^{e_i-1}(p^{e_i}-1)$$

Now to finish: One can verify that 1,2,3,4,5,6 are found in the first 15 tries. But 7 will not ever occur, because $$\displaystyle \phi(n)$$ cannot be 14.

$$\displaystyle 14=2\cdot 7 = 3^0(3-1)\cdot (???)$$. $$\displaystyle 7=p^{s-1}(p-1)$$, or any product of such factors is an impossibility.

#### Jomo

##### Elite Member
Now to finish: One can verify that 1,2,3,4,5,6 are found in the first 15 tries. But 7 will not ever occur, because $$\displaystyle \phi(n)$$ cannot be 14.

$$\displaystyle 14=2\cdot 7 = 3^0(3-1)\cdot (???)$$. $$\displaystyle 7=p^{s-1}(p-1)$$, or any product of such factors is an impossibility.
Nicely done.