Find all the integers $x$ with the property $43x\equiv _{73} 1$. 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.
 A: 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).
