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

If one solves the Diophantine equation $cx + by = a$; i.e., $cx = a - by = a \pmod{b}$ formally, then the answer is $x = (a/c) - (b/c)y$, but the integer character and information is lost and not easily recovered. However, the formula, which I have given at this question characterizes the countably infinite many solutions. Is there any mathematician to generalize this statement?

share|cite|improve this question

Your observation here and in the prior question essentially amounts to the following well-known fact. If $\rm\:b,c\:$ are coprime then $\rm\: e' = b^{\phi(c)}\:$ satisfies $\rm\: e'\equiv 0\pmod{b},\ e'\equiv 1\pmod{c}\:.\ $ Therefore, $\ $ using $\rm\:e'\:$ and its complement $\rm\:\ e = 1-e'\:,\ $ with $\rm\ \ e\: \equiv 1\pmod{b},\:\ e\:\equiv 0\pmod{c}\:,\:$ yields the following closed-form for solutions of congruences by the Chinese Remainder Theorem (CRT)

$$\begin{eqnarray}\rm x\ \equiv\ a\pmod{b} \\ \rm x\ \equiv\ d\pmod{c}\end{eqnarray}\rm\ \ \iff\ \ x\ \equiv\ a\ e + d\ e'\pmod{b\:c}$$

Similar remarks holds for solutions of related congruences. If you go on to study ring theory you will learn that systems of idempotents such as $\rm\:e,\:e'\:$ above are very intimately connected to factorizations (of numbers or rings), e.g. see the Peirce decomposition.

share|cite|improve this answer
Yes I got it. Thanks to BILL DUBUQUE – Gandhi Aug 23 '11 at 15:24

Use the extended Euclidean algorithm.

share|cite|improve this answer
If you don't mind, show once. – Gandhi Aug 22 '11 at 18:55
apply for my problem and show the result – Gandhi Aug 22 '11 at 18:56

You can see my answer to a similar question (linear diophantine eqn with 4 variables) using euclidean algorithm for the generalization.

share|cite|improve this answer

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.