Find all the integers $x$ with the property $43x\equiv _{73} 1$.

Question

I'm asked to find all integers $x$ such that $43x\equiv _ {73}1$. I know how to solve these kinds of problems by plugging in all numbers smaller than $73$, as done in this post, but because of how large $73$ is I'm guessing there must exist a simpler approach.

Answer 1

Indeed there is - and it's suggested in comments. I'll do this example with you though.

Here's the idea: we want to find numbers such that

$$43 x = 1 + 73 k$$

Now, if this were just a linear equation, like $2x =3,$ we would just divide by $2$ on both sides and read off the answer. We could do something similar if we could find an integer $y$ such that $y (43) = 1 + 73 j,$ because then

$$y (43 x) = y + 73yk$$

would simplify to

$$ x + 73jx = y + 73yk$$

or, collecting multiples of $73,$

$$x =_{73} y$$

So now we just need to find a number $y$ such that $43y =_{73} 1.$ We'd get this for free if we could find $a,b$ such that

$$43a + 73b = 1$$

Since $1$ is the gcd of $43,73,$ this is exactly what we'll find when unwrapping the euclidean algorithm. So we compute:

$$(73, 43) = (30, 43) = (30,13) = (4, 13) = (4,1) = 1$$

keeping track of our operations:

$$(73, 43) = (73-43, 43) = (73-43, 43 - (73-43)) = ( 73-43- 2(2(43)-73), 2(43) - 73)$$ $$= (-5(43) + 3(73), 2(43) - 73 - 3(-5(43) + 3(73)))$$

So after simplifying this last term, we find $1 = 17(43) - 10 (73),$ and therefore $y=17$ (take mod 73 to see this).