The questions are:
i) Find $\gcd(315, 495)$
ii) Find $x$ such that $495x \equiv 90 \pmod{6}$ or explain why it does not exist
I did (i) and got $\gcd(315, 495)=45$. How do I find the answer for (ii)? How is it related to (i)?
Here's my attempt for (ii): (I did not use the equation in (i))
$495x \equiv 90 \mod{6}$
whereby $495 \equiv 3 \pmod{6}$
$$3x \equiv 90 \pmod{6}$$
$$3x \equiv 0 \pmod{6}$$
Hence, the smallest integer of $x$ is $2$?
I would like to know if there's a solution that uses the equation in (i)
Best Answer
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{)}.$$