Prove that $\gcd(30m + 5, 11m + 4)|65$ and find the least value of $m \in \mathbb{N}$ such that $\gcd(30m + 5, 11m + 4) = 65$ I have been having trouble with this question for a long time, I just can't seem to see the "trick" that I know is looking me dead in the face. Any nudges in the right direction would be helpful! 
$$\gcd(30m + 5, 11m + 4)|65 \text{ and find the least value of } m \in \mathbb{N}$$ such that $$\gcd(30m + 5, 11m + 4) = 65$$
 A: @The_Big_Cat After working on it for an hour I finally got it.
The proof basically uses the fact that $$\gcd(a,b) = \gcd(a, b+ka) = \gcd(a, b-ka)$$
I am using $(a, b)$ for $\gcd(a, b)$ from here.
We have to prove that $\gcd(30m+5, 11m+4)|65$. Let $d = (30m+5, 11m+4)$.
$$(30m+5, 11m+4)$$
$$= (30m+5 - 3\cdot (11m+4), 11m + 4)$$
$$=(3m+7, 11m+4)$$
$$=(3m+7, 2m-17)$$
$$=(m+24,2m-17)=(m+24, m-41)$$
$$=(m+24-1\cdot (m-41), m-41)$$
$$=(65, m-41)$$
Now we know that $d|65 \implies d| \gcd(30m+5, 11m+4) $. And we have proved the proposition.
Now for the second question. We want $d=65$. Consider the fact that every number divides 0. So if we choose $m=41$ then $\gcd(65, 41-41) = 65$.
Hence, 41 is the smallest such number.
Hope you found the answers useful.
A: Let us call $d=\gcd(30m + 5, 11m + 4)$. 
Observe that 
$$\color{red}{-11}(30m + 5) + \color{blue}{30}(11m + 4)=65.$$
This means a linear combination of the two expressions is $65$, thus  $d$ divides $65$.
Note that
$$\color{red}{-11}\left(\frac{30m + 5}{65}\right) + \color{blue}{30}\left(\frac{11m + 4}{65}\right)=1.$$
For $d=65$, we need both
$$\frac{30m + 5}{65} \in \mathbb{Z} \quad \text{ and } \quad \frac{11m + 4}{65} \in \mathbb{Z}$$
These give
\begin{align*}
m & \equiv 2 \pmod{13}\\
m & \equiv 41 \pmod{65}.
\end{align*}
Thus $m=41$ is the smallest positive integer for which $d=65$.
