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 happens 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.
Thanks in advance for any help you can provide.
$\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)$