Solving for $x$ in modular equation Let's say I have $2 \equiv 35x \bmod 71$. Wolfram tells me $x=67$ but how can I solve this without guessing and checking from $0$ to $71$? What if the variable is an inverse?
 A: $\!\bmod 71\!:\,\ x\equiv \dfrac{2}{35}\equiv \dfrac{4}{70}\equiv \dfrac{4}{-1} \equiv 67\ $ by Gauss's algorithm.
Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.
See this answer for a handful of ways to compute modular fractions.
A: In general, you have to use the extended Euclidean algorithm to find modular inverses. For the problem at hand, there is a shortcut because $35$ and $71$ are closely related:
$2 \equiv 35 \bmod 71 \implies 4 \equiv 70x \equiv -x \bmod 71 \implies x \equiv -4 \equiv 67 \bmod 71$
A: to sum up my comments:


*

*you can rewrite it as 2=71y+35x

*this tells you that both y and x are same parity mod 2 via even=odd+odd=even+even

*rearrangement gets you that x and y have to be of opposite sign through -35x=71y-2

*Further rearrangement gets you $y=-{35\over71}x+{2\over71}$  which gives a line of slope of$-{35\over71}$ which means if you increase x by 71 you decrease y by 35.

*this implies that if one value of x solves the equation with y an integer, so will all values with remainder x when dividing by 71

*$71-1=2\cdot 35$, and that means $2\cdot 71-2=4\cdot 35$ 

*this then implies that x=-4 works ( owing to negative times negative  is positive)

*adding 71 we get 67 as expected and we can then show that adding 71 to this is also a solution. so the answer is x has a remainder of 67 when divided by 71. 

