Take the 2-minute tour ×

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

3 Answers 3

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|improve this answer
Yes I got it. Thanks to BILL DUBUQUE –  Gandhi Aug 23 '11 at 15:24

Use the extended Euclidean algorithm.

share|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|improve this answer

Your Answer


