0
$\begingroup$

How can I solve the linear congruence $7x+3 \equiv 4x+1 \pmod{10}$?


I got:

$7x+3 \equiv 4x+1 \pmod {10} :\iff 10\mid (3x+2) \implies \exists k\in \mathbb{Z} : 10k-3x=2$

I want to apply Bézout's identity to find $x$, but therefore I have to get rid of the $2$ and instead have a $1$. Can I just divide by $2$?

$\endgroup$
5
  • $\begingroup$ See the linked dupes for many methods to solve such linear congruences (or, equivalently, compute modular fractions). $\endgroup$ – Bill Dubuque May 9 '20 at 16:15
  • $\begingroup$ Not sure who you would "divide by 2" but you could solve $10k - 3y = 1$ and multiply by $2$ to get $10(2k)-3(2y) = 2$ and $x=2y$. Or alternatively you can think. $10k$ and $2$ are even so $3x$ is even so $x$ is even so $5k-3(\frac x2)=1$ and solve for $\frac x2$. ... In general, if $\gcd(a,b)=1$ you can always solve $ax + by=k$ but solving $aw+bz=1$ and multiplyig $(w,z)$ by $k$. $\endgroup$ – fleablood May 9 '20 at 16:39
  • $\begingroup$ We need to divide by $3$ not $2$, i.,e. $\, 3x+2\equiv 0\iff x \equiv -2/3\equiv -12/3\equiv -4\equiv 6,\,$ see the dupes. $\endgroup$ – Bill Dubuque May 9 '20 at 16:40
  • $\begingroup$ But you are in some sense dividing by $2$ if you compute $\,-2/3$ as $-2 \times 1/3$ then compute the inverse of $3$ some way, then scale the inverse by $-2$. You can do the equivalent manipulation with the Bezout equation (vs. fractions as @fleablood mentions). Such Bezout scaling is a common way to solve linear Diophantine equations and CRT solutions, e.g. see here and here. $\endgroup$ – Bill Dubuque May 9 '20 at 16:52
  • $\begingroup$ More generally we can compute modular fractions by factoring them into "simpler" fractions, e.g. see here and here. The fractional approach for such is more intuitive than manipulating congruences since it uses well-known operations on fractions (in fact we can do the extended Euclidean algorithm more simply with (multivalued) modular fractions, as I explain there). $\endgroup$ – Bill Dubuque May 9 '20 at 16:59
2
$\begingroup$

All the equivalences are mod $10$:

$$3x+2 \equiv 0 \Leftrightarrow 3x \equiv 8 \Leftrightarrow x \equiv 8(3)^{-1} \equiv 56 \equiv 6.$$

$3$ is invertible because it is coprime to $10$ and it has inverse $7$. So any integer $x$ that is equal to $6$ mod $10$ satisfies what you want.

$\endgroup$
4
  • $\begingroup$ So $7x+3\equiv 4x+1 \pmod{1} \iff 3x\equiv -2 \pmod{10} \iff 3x \equiv 8 \pmod{10} \implies x\equiv 8(3)^{-1}\equiv 6$ is totally fine? $\endgroup$ – Analysis May 9 '20 at 16:12
  • $\begingroup$ Yes, the last arrow is also an equivalence. $\endgroup$ – M. Wang May 9 '20 at 16:13
  • $\begingroup$ Thank you, Sir. $\endgroup$ – Analysis May 9 '20 at 16:14
  • $\begingroup$ @Parabolic Good eye, it is essential to note that since invertible transormations were applied the arrows are all bidirectional (else the solution could be extraneous e.g. here). $\endgroup$ – Bill Dubuque May 9 '20 at 16:23

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