Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $a, b$ and $c$ be positive integers with $\frac{b}{c}$ reduced. Consider the set of rationals, \begin{align} X(a,b,c) = \left \{ \frac{c(a-k)}{ab} \right \}_{k = 1}^{a-1}. \end{align}

Question: How many integers are in the set $X(a,b,c)$ in terms of $a, b$ and $c$?

For example, there are $\gcd(a,c)-1$ integers in $X(a,1,c)$.

Edit: More generally, suppose we consider instead \begin{align} X(a,b,c,e) = \left \{ \frac{c(a-ek)}{ab} \right \}_{i = 1}^{\lceil \frac{a}{e} \rceil - 1} \end{align} with $\frac{e}{a}$ reduced. How many integers are in the set $X(a,b,c,e)$ in terms of $a, b, c$ and $e$?

share|improve this question

1 Answer 1

Let $d = ab/\gcd(ab,c)$. Then you just need integers among $(a-k)/d$, $k=1,2,\ldots,a-1$, which is $\lfloor \frac{a-1}{d}\rfloor = \lfloor \frac{(a-1)\gcd (ab,c)}{ab} \rfloor$. For $b=1$, this reduces to $\gcd (a,c) - 1$.

If $b/c$ is reduced, then $\gcd (ab,c) = \gcd (a,c)$.

share|improve this answer
    
Thanks! I added a slightly more general scenario to the original question. –  user02138 Jan 31 '13 at 5:48
2  
Things get a bit more complicated when you add the variable $e$. You need to find number of $k$ for which $\frac{a-ke}{d}$ is an integer, which is same as solving the linear congruence $ek \equiv a \mod d$. Look at this regarding its solutions. –  polkjh Jan 31 '13 at 7:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.