How do I solve $32x \equiv 12 \pmod {82}$? I am able to solve simpler linear congruences, for example $3x \equiv 2 \pmod 5$. What I would do in this case is use that $0 \equiv 10 \pmod 5$ and then utilising a theorem: $3x \equiv 12 \pmod 5$. Then I can divide by $3$ leaving me $x \equiv 4 \: \left( \mathrm{mod} \: {\frac{5}{\mathrm{GCD}(5,3)}} \right) \quad \Longleftrightarrow x \equiv 4 \pmod{5}$ which means the solution is $x = 4k + 5$ where $k \in \mathbb{Z}$.
But I cannot apply the same method to this congruence:
$$ 32x \equiv 12 \pmod {82} $$
This is how far I got:
$$ 8x \equiv 3 \: \left( \mathrm{mod} \: \frac{82}{\mathrm{GCD}(82, 4)} \right) $$
$$ \Updownarrow $$
$$ 8x \equiv 3 \pmod {41} $$
What could I do next? Please provide solutions without the Euclidean algorithm.
EDIT:
What I found later is that I can say that
$$ 0 \equiv 205 \pmod {41} $$
And then I can add it to the congruence in question and divide by $8$.
So I guess my question is essentially 'How can I find a number that is a multiple of $41$ (the modulus) and which, if added to $3$ gives a number that is divisible by $8$?'
I reckon the Euclidean algorithm is something which gives an answer to these kinds of questions?!
 A: Hint :you can do like this $$\quad{8x \equiv 3 \pmod {41}\\
8x \equiv 3+41 \pmod {41}\\8x \equiv 44 \pmod {41} \div4 \\
2x \equiv 11 \pmod {41}\\2x \equiv 11+41 \pmod {41}\\2x \equiv 52 \pmod {41}\div 2\\x \equiv 26 \pmod {41}\\x=41q+26}$$
A: You just have to find the inverse of $8$ modulo $41$. 
The general method uses the extended Euclidean algorithm, but in the particular case, it's much simpler: from $5\cdot  8=40\equiv -1\mod 41$, you get at once that $8^{-1}\equiv -5\mod 41$, so 
$$x\equiv -5\cdot 3=-15\equiv 26\mod 41.$$
A: basically you are asking how to solve $\frac 1n \mod m$ where $\gcd(m,n)=1$
where $\frac 1n \mod m$ is notation for the  $x$ so that $n*x \equiv 1\mod m$.
Let $m = k + qn$ then $nx = 1 + Zm = 1 + Z(k + qn)$ implies
$x = \frac 1n + \frac {Zk}n + Zq$ where $n|Zk + 1$
Ex.  $x \equiv \frac 17 \mod 67$.  As $67 = 9*7 + 4$ then
$x = \frac {1+Z*4}{7} + 9$
Which means we have to find $Z \equiv -\frac 14 \mod 7$.
Oh... I guess this is Euclid's algorithm.
$7 = 3 + 4$
So $-Z = \frac{1+ 3Y}4 + 1$
Which is clearly $Y =1$ and $-Z \equiv 2\mod 7$ and $Z \equiv -2 \mod 7$
and $x = \frac {1 + 4*(-2)}7 + (-2)*9 \equiv -19 \mod 67$.
And indeed $7*(-19) \equiv -133= (-1)*67 + 1 \equiv 1 \mod 67$ 
... Yeah, you need Euclid's alogrithm.
A: $$
32x\equiv12\pmod{82}
$$
is equivalent to
$$
16x\equiv6\pmod{41}
$$
and since $(41,2)=1$, we can divide by $2$
$$
8x\equiv3\pmod{41}
$$
Then noting that $5\cdot8\equiv-1\pmod{41}$, we get that $36\cdot8\equiv1\pmod{41}$. Multiplying both sides by $36$ yields
$$
\bbox[5px,border:2px solid #C0A000]{x\equiv26\pmod{41}}
$$
Note: When looking for the inverse of $a$ mod $m$ it is often a good idea to see if $a\mid(m-1)$ or $a\mid(m+1)$; if either of these hold, they give a quick inverse mod $m$: $a^{-1}\equiv-\frac{m-1}a$ or $a^{-1}\equiv\frac{m+1}{a}$. Above, it was noted that $8|(41-1)$ leading to $8^{-1}\equiv-\frac{41-1}8\pmod{41}$.

Alternate Method of Finding the Inverse of $\boldsymbol{8\pmod{41}}$
Since $41$ is prime and $(41,8)=1$, we know, by Fermat's Little Theorem, that $8^{39}\equiv8^{-1}\pmod{41}$. We can compute $8^{39}\pmod{41}$ using the Square and Multiply Algorithm. $39=100111_\text{two}$, therefore,
$$
\begin{align}
8^1&\equiv8&\pmod{41}\\
8^2&\equiv23&\pmod{41}&&\text{square}\\
8^4&\equiv37&\pmod{41}&&\text{square}\\
8^8&\equiv16&\pmod{41}&&\text{square}\\
8^9&\equiv5&\pmod{41}&&\text{multiply}\\
8^{18}&\equiv25&\pmod{41}&&\text{square}\\
8^{19}&\equiv36&\pmod{41}&&\text{multiply}\\
8^{38}&\equiv25&\pmod{41}&&\text{square}\\
8^{39}&\equiv36&\pmod{41}&&\text{multiply}\\
\end{align}
$$
Therefore, $8^{-1}\equiv36\pmod{41}$.
A: OK, without the Euclidean algorithm, you are looking for some $k$ such that $8$ divides $41k+3$, which gives you a new equation in smaller numbers (which is a Euclidean algorithm idea too, but still):
$$41k+3\equiv 0  \bmod 8 \\ 
41\equiv 1 \bmod 8 \\
k+3 \equiv 0 \bmod 8 \\
k\equiv 5 \bmod 8$$
So then you have your $41\times 5 = 205$ to make the divisibility.
A: $\, 8x = 3\!+\!41n\!\iff\!\bmod 8\!:\  0\equiv 3\!+\!41n\equiv 3\!+\!n\!\iff\! n\equiv -3\,$ so $\,x\equiv \frac{3+41(-3))}8\equiv -15\equiv 26$
Alternatively $\bmod 41\!:\ x\equiv \dfrac{3}{8}\equiv \dfrac{15}{40}\equiv\dfrac{15}{-1}\equiv 26\ $ by  Gauss's algorithm
Alternatively $ \bmod 41\!:\ x\equiv \dfrac{3}{8}\equiv \dfrac{44}{8}\equiv \dfrac{11}{2}\equiv\dfrac{52}{2}\equiv 26\ $ by adding $\pm 41$ to simplify divisions
Alternatively $\bmod 41\!:\ x\equiv \dfrac{1}8\,\dfrac{3}1\equiv \dfrac{-40}8\ \dfrac{3}1\equiv  (-5)3\equiv -15$
Remark $ $ The first method essentially uses a single step of the (extended) Euclidean algorithm, and the second is a special case of  that for prime moduli. The other methods are ad-hoc - they try to massage the fractions by adding small multiples of the modulus to make quotients exact / simpler.
Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.
A: $32x \equiv 12 \pmod{82} \; \text{ iff }$
$\quad (\exists \, x, k \in \Bbb N)\, [ 0 \lt x \lt 82 ; \land \; k \gt 0 \; \land \; 32x = 12 + 82k\,]$
Employing Euclidean division,
$\quad 82 = 32 \cdot 2 + 18$
So,
$\quad 32x = 12 + 32 \cdot (2k) + 18k$
Using this 'reduction pattern' we employ the corresponding algorithm:
$\alpha-$Solve:
$\;32x \equiv 12 \pmod{82}, \text{ and } \; 82 = 32 \cdot 2 + 18,\quad -12 + 32 = 20$
$\alpha-$Solve:
$\;18x \equiv 20 \pmod{32}, \text{ and } \; 32 = 18 \cdot 1 + 14,\quad -20 + 2\cdot 18 = 16$
$\alpha-$Solve:
$\;14x \equiv 16 \pmod{18}, \text{ and } \; 18 = 14 \cdot 1 + 4,\quad -16 + 2\cdot 14 = 12$
$\alpha-$Solve:
$\;4x \equiv 12 \pmod{14}, \text{ ANS: } \; x = 3 \text{ is the least residue solution}.$
Propagating backward,
Solve $14x = 16 + 3 \cdot 18, \text{ ANS: } \; x = 5$
Solve $18x = 20 + 5 \cdot 32, \text{ ANS: } \; x = 10$
Solve $32x = 12 + 10 \cdot 82, \text{ ANS: } \; x = 26$
$\text{ANSWER: }  x = 26 \text{ is the least natural number satisfying }$
$\quad 32x \equiv 12 \pmod{82}$
A: \begin{align}
   32x &\equiv 12 \pmod {82} &\text{Divide by $2$}\\
   16x &\equiv 6 \pmod {41} 
       &\text{Divide by $2$. ($2^{-1}$ exists since $\gcd(2,41)=1$)}\\
   8x &\equiv 3 \pmod {41} &\text{$3 \equiv 3+41 \pmod{41}$}\\
   8x &\equiv 44 \pmod {41} &\text{divide by $4$}\\
   2x &\equiv 11 \pmod {41} &\text{$11 \equiv 11+41 \pmod{41}$}\\
   2x &\equiv 52 \pmod {41} &\text{Divide by $2$} \\
   x &\equiv 26 \pmod {41}
\end{align}
