0

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$?

Analysis
  • 2,228
  • 6
  • 16
  • See the linked dupes for *many* methods to solve such linear congruences (or, equivalently, compute modular fractions). – Bill Dubuque May 09 '20 at 16:15
  • 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$. – fleablood May 09 '20 at 16:39
  • 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. – Bill Dubuque May 09 '20 at 16:40
  • 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](https://math.stackexchange.com/a/3290965/242) and [here](https://math.stackexchange.com/a/2060729/242). – Bill Dubuque May 09 '20 at 16:52
  • More generally we can compute modular fractions by factoring them into "simpler" fractions, e.g. see [here](https://math.stackexchange.com/a/2368266/242) and [here](https://math.stackexchange.com/a/3434593/242). 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). – Bill Dubuque May 09 '20 at 16:59

1 Answers1

2

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.

M. Wang
  • 879
  • 5
  • 13
  • 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? – Analysis May 09 '20 at 16:12
  • Yes, the last arrow is also an equivalence. – M. Wang May 09 '20 at 16:13
  • Thank you, Sir. – Analysis May 09 '20 at 16:14
  • @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](https://math.stackexchange.com/a/741172/242)). – Bill Dubuque May 09 '20 at 16:23