4
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ Are you sure you wrote the question right. $\endgroup$
    – fleablood
    Commented Feb 12, 2019 at 8:56

2 Answers 2

3
$\begingroup$

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{)}.$$

$\endgroup$
1
  • $\begingroup$ thank you! i get it now $\endgroup$
    – llamaro25
    Commented Feb 12, 2019 at 9:11
2
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .