I need to find the smallest possible value of x when:
x = 2 mod3 &
x = 3 mod5
My first step was to put it in the form 1 + 3a = 2mod5. It then becomes 3a = 1 mod 5 (presumably because 1 mod 5 = 1?). However the next step should be a = 2 mod5 but I don't understand the step to get to 2 mod5.
On
i would write $$x=2+3m,x=3+5n$$ from here we get $$2+3m=3+5n$$ and we have to solve$$3m-5n=1$$ for integers $$m,n$$ solving this Diophantine equation we obtain $$m=2+5k,n=1+3k$$ from here you will get your solutions
On
You want to solve $3a \equiv 1 \mod 5$ so ...
1) Intuition.
$1 \equiv 6 \mod 5 \equiv 2*3$ so $ a = 2$.
2) Just keep adding $5$ until you get something.
$3a \equiv 1 \mod 5$. but $3\not \mid 1$. So add $5$.
$3a \equiv 1+5 = 6 \mod 5$. And $3|6$ so $a = \frac 63 = 2$.
3) you can do it that hard way:
....
$3a = 1\equiv 5 \implies 3a = 1 + 5k \implies$
$3a = 3k + 1 + 2k \implies 1+2k \equiv 0 \mod 3 \implies 2k \equiv -1 \mod 3$
$\implies 2k = 3m - 1 = 2m + m- 1 \implies$
$m-1 \equiv 0 \mod 2 \implies m \equiv 1 \mod 2$
So let $m = 1$.
Then $2k = 3m - 1 =3-1 = 2 \implies $k = 1$
So $3a = 1 + 5k = 1 + 5 = 6 \implies$
$a = 2$.
The above seems pointlessly tedious, but it is basically Euclid's Algorithm and if $\gcd (3,5) = 1$ willl always work.
For harder cases it is useful but for simple cases your intuition should just tell you.
Less obvious.
$74a \equiv 1 \mod 981$.
Intuition? I have none.
Add $981$ so $74a \equiv 1 + 981 \equiv 982 \mod 981$ ... we could be here all night....
$74a = 1 + 981k = 1 + 13*74k + 19k$ so $19k + 1 \equiv 0 \mod 74$
$19k \equiv -1 \mod 74$ so $19k = -1 + 74m = -1 + 4*19m -2m$
$-1 - 2m \equiv 0 \mod 19$ so $2m \equiv -1 \mod 19$ so $2m = -1 + 19n$
so $2m = - 1 + n + 2*9n$
So $n-1 \equiv 0 \mod 2$
So $n \equiv 1 \mod 2$.
Let $n = 1$. $2m = -1 + 1 + 2*9*1 = 18$ so $m = 9$.
So $19k = -1 + 74m= -1 + 74*9 = 1+666$ (ooh, scary) $ = 665 = 19*35$
So $k = 35$ and $74a = 1 + 981k = 1 + 981*35 = 34336=464*74$
So $a \equiv 464\mod 981$
Hint: Multiply both sides of $3a \equiv 1 \bmod 5$ by $2$.