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