Find x such that $495x \equiv 90 \pmod{6}$ or explain why it does not exist

The common thread between these two questions is that they both involve breaking integers down into their unique prime factor decomposition (using the Fundamental theorem of arithmetic). This allows you to find common factors in the relevant expressions and simplify to obtain solutions.


(i) When you want to find the greatest common divisor of two numbers, the simplest thing to do is to break those numbers down into their unique prime factor decomposition:

$$\begin{equation} \begin{aligned} 315 &= 3^2 \cdot 5 \cdot 7, \\[6pt] 495 &= 3^2 \cdot 5 \cdot 11. \\[6pt] \end{aligned} \end{equation}$$

The greatest common divisor of these two numbers will consist of the shared prime factors, so it is:

$$\text{gcd}(315, 495) = 3^2 \times 5 = 45.$$


(ii) For the latter problem, you are trying to find integers $x$ and $k$ for which:

$$495 \cdot x = 6 \cdot k + 90.$$

Again, we can break the relevant numbers down into their unique prime factor decomposition:

$$3^2 \cdot 5 \cdot 11 \cdot x = 2 \cdot 3 \cdot k + 2 \cdot 3^2 \cdot 5.$$

Eliminating the common factor and grouping terms gives:

$$3 \cdot 5 \cdot 11 \cdot x = 2 \cdot (k + 3 \cdot 5).$$

So a solution is obtained by taking $k=3 \cdot 5 \cdot 10 = 150$ and $x=2$. That is:

$$990 \equiv 90 \quad \text{(mod } 6 \text{)}.$$


I wonder if the question is expecting you to use the fact:

If $\gcd(a,b) = d$ and $a|bm$ then $a|dm$ (as none of the factors other than $d$ will have any factors in common with $a$).

so $495x \equiv 90 \pmod 6$ means

$6|495x - 90 = 45(11x - 2)$ and as $\gcd(6, 45)=3$

$6|3(11x-2)$ so $2|11x - 2$ and so $2|11x$ and so $2|x$.

For any even $x$ we have $495x \equiv 90 \pmod 6$.

.... which seems a pretty convoluted way to do it.

===

Far more straightforward would be

$495x \equiv 90 \pmod 6$

$3x \equiv 0 \pmod 6$

$6|3x$ so $2|x$