This last step makes me go crazy. I'll show you why:
I've got:
$\mathsf 15x \equiv 9 mod 27$
I see i can divide all three numbers by 3, so i proceed obtaining:
$\mathsf 5x \equiv 3 mod 9 $
With the Euclidean Algorithm i proceed to check that $\mathsf MCD(9,5) = 1$
And my inverse is $\mathsf e =2$
Multiplying both sides by $\mathsf e$ gets me to:
$\mathsf 10x \equiv 6 mod 9 $
So i know the solutions have to be in the $\mathsf S= 6+9K$
Now, the solution is 3. I know that 3 is equal to 6-9. But why is it 3 and not 6? When i'm in this step, i really don't know which is the solutions, especially with big mods. I know it has to be x< mod, but i really don't know which one.
Same when i have
$\mathsf 2x \equiv 25mod7$
I do everything, and get to
$\mathsf 6x \equiv 75 mod 7$
75/7 gives me 5 as remainder. So i have
$\mathsf x \equiv 5 mod 7$
And know that the solution has to be $\mathsf 0 \le x < mod$ , but the solution is 2. 2 is equal to 5-7.
When do i have to subtract and when not to?