# Solution

Solve $28x \equiv 30 \pmod{46}$

Translating this back to equation form, we have $28x - 30 = 46n$, or equivalently

$$28x - 46n = 30$$

We should verify that the gcd of $28$ and $46$ divides $30$, which we can do by inspection, noting $gcd(28,46)=2$. Recall, if the gcd didn't divide the $30$, we would have no solution here. If the numbers were bigger, we can use the Euclidean Algorithm to find the gcd -- and in truth, we should do this anyways, as the steps of the Euclidean Algorithm help us solve the congruence:

$$\begin{array}{rl} 46 &= 1 \cdot 28 + 18\\ 28 &= 1 \cdot 18 + 10\\ 18 &= 1 \cdot 10 + 8\\ 10 &= 1 \cdot 8 + \fbox{2} \leftarrow gcd\\ 8 &= 4 \cdot 2 + 0 \end{array}$$

Now we can find a linear combination of $28$ and $46$ that equals the gcd of $2$ by working backwards through the calculations above:

$$\begin{array}{rl} 2 &= 10 - 8\\ &= 10 - (18 - 10)\\ &= 2 \cdot 10 - 18\\ &= 2 (28 - 18) - 18\\ &= 2 \cdot 28 - 3 \cdot 18\\ &= 2 \cdot 28 - 3 (46 - 28)\\ &= 5 \cdot 28 - 3 \cdot 46 \end{array}$$

Hence, $x=5$, $n=3$ solves the simpler equation $28x-46n = 2$.

Since we wish our linear combination of $28$ and $46$ to be fifteen times that (recall $30 = 2 \cdot 15$), we multiply both $x$ and $n$ by $15$ to obtain one solution for the equation we actually care about:

$$x = 75, n= 45 \quad \quad \textrm{is one solution to} \quad \quad 28x - 46n = 30$$

With one solution in hand, finding the rest is immediate:

$$x = 75 + \frac{46}{2} k \quad , \quad n = 45 + \frac{28}{2} k \quad \quad \textrm{where k is an integer}$$ Finally, upon noting that we never really cared about the value of $n$, and only wished to solve the original congruence (which has to do with $x$), and reducing the above in terms of $\pmod{46}$, we have our final solution: $$x \equiv 29 + 23k \pmod{46} \quad \quad \textrm{where k is an integer}$$

or equivalently (since there are only two such non-negative numbers less than $46$),

$$x \equiv 6 \textrm{ or } 29 \pmod{46}$$