2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes I got it. Thanks to BILL DUBUQUE $\endgroup$ – Gandhi Aug 23 '11 at 15:24
0
$\begingroup$

Use the extended Euclidean algorithm.

$\endgroup$
  • $\begingroup$ If you don't mind, show once. $\endgroup$ – Gandhi Aug 22 '11 at 18:55
  • $\begingroup$ apply for my problem and show the result $\endgroup$ – Gandhi Aug 22 '11 at 18:56
0
$\begingroup$

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

https://math.stackexchange.com/a/585548/52487

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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