Suppose $\gcd(a,b)=\gcd(c,d)=\gcd(a,c)=1$. Then, $\{an+b:n\in\mathbb{N}\}\cap\{cn+d:n\in\mathbb{N}\}\neq\emptyset$. Why is that? I think I missed something silly...
25251
We want to find the solution $x$ to the congruence system  $$\begin{align} x &amp;\equiv r_1 \!\!\!\pmod{\!m_1}\\ x &amp;\equiv r_2 \!\!\!\pmod{\!m_2}\end{align},\ \ {\rm where}\ \  \gcd(m_1, m_2) = 1$$  These can be rewritten as  $$\begin{align} x &amp;= r_1 + m_1 j\\ x &amp;= r_2 - m_2k\end{align}$$  for unknown integers $j, k$. So we set those two equations as equal and rearrange them to  $$m_1j + m_2k = r_2 - r_1$$  Now assume we perform $\text{egcd}(m_1, m_2)$, which gives us the solution to  $$m_1u + m_2v = \gcd(m_1, m_2)$$  Let the integer $\,h\,$ make $\,h \gcd(m_1, m_2) = r_2 - r_1$.  Then $\qquad hm_1u + hm_2v = h\gcd(m_1, m_2) =  r_2 - r_1 = m_1j + m_2k$  At this point I am lost because I don't think we can just assume  $hm_1u = m_1j$ and extract $j = hu$.   How do I get the values of $j$ or $k$ so I can get the value of $x$?
83944
I was told to prove $\gcd(ab,c)=1$ then $\gcd(a,c)=1$.  I picked a number $p$ that goes into $ab$ and $c$, so $ab=px$ and $c=py$. but now what?? I tried $abc=p^2xy$ but then I can't.  Please help me!
45763
Let $p$ be a prime. Suppose that $\gcd(a, b) = p$. Find $\gcd(a^2,b)$  for all integers a and b.   I was able to prove that $\gcd(a^2,b^2) = p$ but I don't know if it helps.  Any help is greatly appreciated.
121068
I'm trying to show that if $\operatorname{gcd}(a,b) = 1$, then $\operatorname{gcd}(ab,a+b)=1$.  I've tried  to use the gcd properties: $$\operatorname{gcd}(a,b)=1 \implies  \operatorname{gcd}(a,a+b)=1\\\operatorname{gcd}(a,b)\implies\operatorname{gcd}(ab,b^2)=b$$ but I got stuck. Any hint will help.
51653
Did not find this from this website...  If $$ \gcd(a,b)=1,$$ then there exists integers $x$ and $y$ such that $$xa+yb=1.$$  Now, the tip is to use particular corollary, that states:  The class $[m]_{n}$ generates $\mathbb{Z}/n\mathbb{Z}\Leftrightarrow \gcd(m,n)=1.$  I am totally lost with the corollary.  Let's assume that $\gcd(m,n)=1$. Then, $[m]_{n}$ generates $\mathbb{Z}/n\mathbb{Z}$.  OK! Then what?  There is also follow up, where I have to prove the converse. I am familiar with Bezout's lemma.
96285
Can anyone show some hints to this? If $\gcd(a,b)=1$, then $a^{\phi(b)}+b^{\phi(a)}=1 \pmod{ab}$. I know that $a^{\phi(b)}=1 \pmod{b}$, and similarly, $b^{\phi(a)}=1 \pmod{a}$, but then how do I combine the work so that I get the result I need? Thanks!
4816
Could someone please help me with this proof?     Suppose that $a, b \in N$, and $d = \gcd(a, b)$. Since $d$ divides $a$, we have $a = de$ for some integer $e,$ and similarly $b = df$ for some integer $f$. Prove that $\gcd(e, f) = 1$.   I understand why it works. Since d is all the common factors of $a$ and $b, e$ and $f$ had no common factors, therefore the $\gcd(e,f) = 1$. But how do I prove this?  Thanks in advance.
69274
If  $a,b$ are positive integers such that $\gcd(a,b)=1$, then show that $\gcd(a+b, a-b)=1$ or $2$ and $\gcd(a^2+b^2, a^2-b^2)=1$ or $2 $. Progress We have   $\gcd(a,b)=1\implies \exists u,v\in \mathbb Z$ such that $au+bv=1\implies a^2u'+bv'=1, u',v'\in \mathbb Z$. Let $\gcd(a+b, a-b)=d$. Then $\mid (a+b)x+(a-b)y, \forall x,y\in \mathbb Z$. How to show $\gcd(a+b, a-b)=1$ or $2$ and $\gcd(a^2+b^2, a^2-b^2)=1$ or $2 $.
45033
I don't really know how to prove this, i suppose it must have something to do with the definition of greatest common divisor and Bézout's identity.  I looked at some other questions here and thought that i had to get to gcd(ma+nb,mn)=1 and that gcd(a,n)gcd(b,m)=1 too, but i'm not sure.
34036
Prove for positive integers $a,b,c$ and $d$  (where $b  \neq 0$ , $d \neq 0$ and $b \neq d$), if $\gcd(a,b) = \gcd(c,d) = 1$, then $\frac{a}{b} + \frac {c}{d}$ is not an integer.  I understand that if $\gcd(a,b)$ and $\gcd(c,d) = 1$, at least one number in each pair is a prime or is $1$. As for after that, I'm totally stumped, could I get some tips, clues, help?
24558
How to show that     $$ \gcd\bigg( {a^n-b^n \over a-b} ,a-b\bigg )=\gcd(n d^{n-1},a-b ) $$    $a,b\in \mathbb Z$   where $d=\gcd(a,b)$?    Note $\ $ Some of the answers below were merged from . The answers (and their comments) may depend on context provided in that question.
121669
I did:  $$gcd(84,5) = \\ 84 = 5*16+4 \\ 5=4*1+1$$  $$4 = 84-5*16 \\ 1 = 5-4*1 \\ 1 = 5-(84-5*16)\\ 1 = 17*5-1*84$$  So the answer should be $1$ but it's 4, what went wrong?
8732
If $\gcd(a,b) = 1$ and $a,b\mid x$ then $ab\mid x$.  My attempt at answering the question:  \begin{align*} x &amp;\equiv 0 \pmod{a}\\\ &amp;\Longrightarrow x\text{ is divisible by $a$}\\\ &amp;\Longrightarrow x = ma\text{ for some integer $m$}\\\ \ \\\ x &amp;\equiv 0 \pmod{b}\\\ &amp;\Longrightarrow  x\text{ is divisible by $b$}\\\ &amp;\Longrightarrow x = mb\text{ for some integer $m$}\\\ \ \\\ x^2 &amp;= (ma)(mb)\\\ x^2 &amp;= (m^2)(ab)\\\ x &amp;= \sqrt{m^2ab}\\\ x &amp;= m\sqrt{a}\sqrt{b} \end{align*} Let $m$ be $k\sqrt{a}\sqrt{b}$. Then \begin{align*} x &amp;= kab\\\ &amp;\Longrightarrow x \equiv 0 \pmod{ab} \end{align*}  Is this correct, if not can someone point me in the right direction?
66002
How would you show that if $ac≡bc$ $\mod m$ and $\gcd(c,m)=d$, then  $a≡b$ $\mod \frac{m}{d}$?  Any help would be much appreciated!
60229
Say $a$ and $b$ are integers. $\gcd(a,b)$ is then $d$. Now if $a$ equals $dm$ for some integer $m$ and b equals $dn$ for some integer n, how come the gcd of this m and n is always 1?
102709
Prove that if $a, b$ are both even then $\gcd(a,b) = 2\cdot\gcd(a/2,b/2)$.   Little confused here. I have tried the following but it's basically just repeating the proof unfortunately:   $a = 2 \cdot a_1 $ and $ b = 2 \cdot b_1$ (Take factor of 2 out)  $d = \gcd(a,b)$  $d = 2\gcd(a_1, b_1)$ $a/2 = a_1$ and $b/2 = b_1$   I've even confused myself! Could someone help!
72040
Show that if $fd'=f'd $ and the pair $f, d $ are coprime, that is gcd($d,f $)=1, as is the pair $f',d' $, then $f=f' $ and $d=d' $.  This should be simple, but I couldn't verify it. Thanks in advance!