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

[Steven G]

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]

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.

 

[Steven G]

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.