Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer
Thanks! I added a slightly more general scenario to the original question. – user02138 Jan 31 '13 at 5:48
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


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.