# Goldbach Conjecture: Subsets of the Euler Totient Function

So... I was toying around with the Goldbach Conjecture, and I came to a very interesting puzzle, related to the Euler Totient Function, φ(n). For those of you who don't know it, Wikipedia has a pretty good description.

My question is a little bit open-ended, because there's a lot of ways this could go:

Suppose we have a number $(n)$ and prime (p) < sqrt(n) such that (n) is not divisible by (p). Then we could calculate the Totient Function of (pn) to be some constant (k). In other words, φ(pn) = k. Then my question is this: Of these (k) relatively prime numbers, what is the minimum that can be in the first (n) numbers of (pn)? Or another way of phrasing the question: For a given number (n) divisible by a prime (q), what is the fewest possible number of integers less than (n/q) that are relatively prime to (n)?

TO BE CLEAR: I'm not looking for a comparison φ(n), I'm looking for the numbers 'in' φ(pn) that also happen to be less than n. Essentially, I'm looking for the value of φ(n) when we also eliminate everything divisible by an additional factor p.

For example: If n is 10, p could be 3. Then φ(3*10) = 8, so k is 8 and k/p = 8/3. In reality, there are only 2 numbers less than 10 that are relatively prime to 30- 1 and 7. This is different from φ(10), as it does not include 3 or 9.

My hope is to show that the real value can be no less than half expected value (φ(n)/q), though I don't know if this is true.

• Just to see if I got it right. You have a prime $p$, and a natural number $n$, with $p < \sqrt{n}$. You want to show that $\{ x : 0 \le x < n, \gcd(x, p n) = 1 \}$ has no more than $\phi(pn)/p$ elements? – Andreas Caranti Feb 20 '17 at 8:26
$\phi(p) = p-1$ (for $p$ prime) and $\phi$ is multiplicative between coprime numbers, so $\phi(pn)=(p-1)\phi(n)$. Additionally of the totatives of $n$ we will only lose multiples of $p$, and only those that are also coprime to $n$ of course. So the value you are seeking should be no less than $\phi(n) -\frac {n(p-1)}p$ as I understand your question. Of course for $n$ odd and $p=2$ this could be large drop... say $n=15, p=2$ we go from $(1,2,4,7,8,11,13,14)$ to $(1,7,11,13)$ but the overlap of numbers already covered by the prime factors of $n$ does appear to keep the total loss limited to no more than half of $\phi(n)$