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.

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 $m$ be a positive integer. Let $a,b$ be integers with $0 \leq a,b < m$, $a,b$ not both zero, $\gcd(a,b,m)=1$.

Do there necessarily exist integers $x,y$ such that
$x \equiv a \pmod{m}$
$y \equiv b \pmod{m}$

Equivalently, are there integers $c,d,k,l$ such that $$ c(a+mk) + d(b+ml)=1? $$

EDIT: Consider two refinements.
1. What conditions on $a,b$ are necessary?
2. What if $m$ is prime?

share|cite|improve this question
You need $\gcd(a,b,m)=1$ at least. – anon Jan 23 '12 at 23:09
Thanks for pointing these things out. I've edited the question accordingly. – reachout Jan 23 '12 at 23:20
That $p$ in the first line isn't defined and never shows up again - was it supposed to be $m$? – Gerry Myerson Jan 24 '12 at 0:05
@GerryMyerson: Fixed. – reachout Jan 24 '12 at 0:07
up vote 2 down vote accepted

Let $t$ be the product of all the primes dividing $b$ but not $a$ (if there are no such primes then $t$ is the empty product which, by convention, is $1$). Let $x=a+tm$, $y=b$. Then clearly $x\equiv a\pmod m$, and $y\equiv b\pmod m$, so we just have to check that $\gcd(x,y)=1$.

Let $p$ divide $y$. If $p$ also divides $a$, then it doesn't divide $t$, by the construction of $t$, and it doesn't divide $m$, since $\gcd(a,b,m)=1$, so it doesn't divide $tm$, so it doesn't divide $x=a+tm$. If $p$ doesn't divide $a$, then it does divide $t$ (by construction of $t$), so it divides $tm$, so again it doesn't divide $x=a+tm$. So no prime dividing $y$ divides $x$, so $\gcd(x,y)=1$.

Historical note: Andrzej Schinzel showed me this idea in 1976.

share|cite|improve this answer

Suppose that $a$ and $m$ are relatively prime, and also $b$ and $m$. (This is a more stringent condition than what you want.)

By Dirichlet's Theorem on primes in arithmetic progressions, there are infinitely many primes of the form $a+sm$, also infinitely many primes of the form $b+tm$. So in fact there are distinct primes $x$ and $y$ that satisfy your conditions.

Undoubtedly gross overkill! But at least we get the strong answer that in this case we can make $x$ and $y$ prime.

More or less the same argument holds if at least one of $a$ and $b$ is relatively prime to $m$, say $b$. There are infinitely many primes of the form $b+tm$, so pick $x=a$, and $y$ any prime of the right shape that does not divide $a$.

share|cite|improve this answer
This solves the $m$ prime case completely. – maxpower Jan 24 '12 at 0:13
It is overkill - Dirichlet is not needed, as per the answer I have just posted. – Gerry Myerson Jan 24 '12 at 0:18
@Gerry Myerson: I was being lazy. – André Nicolas Jan 24 '12 at 0:19

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.