For $\gcd(p.q)=1$ and $\gcd(r,s)=1$ show $\gcd(ps,rq)=1$.  I tried via contradiction. Let $\gcd(ps,rq) \neq 1$, so let $d &gt; 1$ a common divisor of $ps$ and $rq$, i.e. $ps = dx$ and $rq = dy$ for some integers $x,y$. So $ p = \frac{dx}{s} $ and $q = \frac{dy}{r}$. It follows $\gcd(p,q) = \gcd(\frac{dx}{s}, \frac{dy}{r}) \geq d &gt; 1$. That should do it, but I don't think the last but one inequality holds. If $s \nmid x$ or $r \nmid y$ this won't work... Might be the wrong way, but I would be very thankful, if someone could help me!
120786
If $\gcd(m,n)=1$, and $\gcd(a,m)=\gcd(b,n)=1$, then $\gcd(ab, mn)=1$.  I tried going about it algebraicallly using the definition of GCD, which gave me $$\left(a u_2+m v_2\right) \left(b u_3+n v_3\right) \left(m u_1+n v_1\right)=1$$ which, when expanded, gives $$a b m u_1 u_2 u_3+a b n u_2 u_3 v_1+a m n u_1 u_2 v_3+a n^2 u_2 v_1 v_3+b m^2 u_1 u_3 v_2+b m n u_3 v_1 v_2+m^2 n u_1 v_2 v_3+m n^2 v_1 v_2 v_3.$$ Unfortunately, factoring with respect to $mn$ and $ab$ does not give me an equation of the form $mnx+aby=1$, as I had hoped.  Then I tried going another route: Assume that $\gcd(ab,mn)=d\neq1$. Then there is a prime $p$. which divides $uab+vmn=d$. Since $p|d$ and $d|mn$ and $d|ab$, $p|mn$ and $p|ab$. Since $p$ is prime, it either divides $m$ or it divides $n$, but since $\gcd(m,n)=1$, it cannot divide both. Without loss of generality, say $p|m$.  Since $\gcd(m,a)=1$, $p\not|a$. This means that $p|b$. But I don't know how to get a contradiction from here.
23402
(a) Prove $(k,n+k)=1$ iff $(k,n)=1$. (b) Is it true that $(k,n+k)=d$ iff $(k,n)=d$? (all variables are integers, (a,b) means gcd(a,b))  For (a), I can only get so far.  $(k,n+k)=1\ \Rightarrow\ kq_1+(n+k)q_2=k(q_1+q_2)+nq_2=1$.  Note that we don't yet have that theorem (from a different class) that says something like if $d=(a,b)$, then $d$ is the smallest (or is it biggest) number which can be made by $ak_1+bk_2$, (which I'm not quite sure how it would help, anyway). So I'm stuck.
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.
52697
How can I prove that $\gcd(a, b) = \gcd (a, b + ma)$?  I have tried this:  let $g = \gcd(a, b)$, then $g \mid a$ and $g \mid b$. This means that $g \mid ax+by$.  I don't know what to do next.  Thanks.
59641
Let $d=GCD(n^2+5,n^3-5n^2+6n)$ show that $d|630$   My work: $d|n^3+5n,n^3-5n^2+6n\implies\ d|5n^2-n,5n^2+25\implies d|n+25 $ Now I can't go further!!
9261
Hi I'm practicing some number theory and I've come across the following problem,  Suppose $n \geq 1$ is an odd integer that divides $a^2 - 1$ for some integer $a &gt; 1$. Prove that,  $$n = \gcd(a-1, n)\gcd(a+1, n)$$  Now I know that the $\gcd(a-1, a+1) = 1$ if $a$ is even and $2$ if $a$ is odd and I believe this is relevant but I can't solve the problem. I've not really any idea where to start so even just help with that would be great.  Thanks
9789
Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs?  $a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be a common divisor of $a$ and $b$. Then   $$\forall x', y' \in \mathbb{Z}: c | ax' + by'\Longrightarrow\exists q_1, q_2 \in \mathbb{Z}\,\,\, s.t.\,\,\, c q_1 = ax' + by'\,\,,\,\,cq_2 = g$$   So   $$gcd(a, b)=g=c q_2 = c q_1 \frac{q_2}{q_1} = \left(\frac{q_2}{q_1}x'\right)a + \left(\frac{q_2}{q_1}y'\right)b$$ So if we have $q_1|q_2$ then we found $\gcd(a,b)=ax'+by'$ for all $x', y' \in \mathbb{Z}$.  Now   $$\frac{q_1}{q_2}=\frac{c q_1}{c q_2} = \frac{ax'+by'}{g}$$ but $g|a$ and $g|b$ so $\exists q_3 \in \mathbb{Z}: \frac{q_1}{q_2}=q_3 \Rightarrow q_1=q_2 q_3 \Rightarrow q_1 | q_2\,$ . QED.
94081
Assuming that $\gcd(a,b) = 1$, prove that $\gcd(a+b,a^2+b^2) = 1$ or $2$.   I tried this problem and ended up with $$d\mid 2a^2,\quad d\mid 2b^2$$ where $d = \gcd(a+b,a^2+b^2)$, but then I am stuck; by these two conclusions how can I conclude $d=1$ or $2$?  And also is there any other way of proving this result?
41678
As stated in the title, the problem to prove is  Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$.  I think I've proved it, but I would like a second opinion. Here goes:  PROOF Suppose $\exists d \neq 1 \in \mathbb{Z}$ s.t $\gcd(ab,c)=d$. It follows then that $d|ab$ and $d|c$. Now, if $d|a$ but not $b$, then since $d|c$, by linearity we have $d|\gcd(a,c)$. But $\gcd(a,c)=1$ so then $d=1$. The argument for $d|b$ is similar, resulting in $d=1$. Thus, since both cases lead us to $d=1$, we have a contradiction on our hands $\implies$ $ab$ and $c$ must be relatively prime $\implies \gcd(ab,c)=1$. $Q.E.D$  The question: was this a valid argument or do you think I should provide more?
14728
Suppose there are $2$ permutations given by $p$ and $q$. I need to check whether $p$ belongs to the group generated by $q$, and if so, it's representation in a power of $q$. In other words, I've been given $p$ and $q$, I need to check whether $\exists i \in \{ 0,...,|q|-1 \} \text{ such that } p = q^i$ I know that if $m = \gcd(i, |q|)$, then $|q^i| = \frac{|q|}{m}$. Now, say that such an $i$ exists. Then, $$ |p| = \frac{|q|}{\gcd(i, |q|)} \Rightarrow \gcd(i, |q|) = \frac{|q|}{|p|} $$ Thus, a necessary condition for such an $i$ to exist is: $|p|$ divides $|q|$ Say that this holds, and $\frac{|q|}{|p|} = r$, where r is an integer. Then we just have to solve $\gcd(i, |q|) = r$ for $ i \in \{ 0,...,|q|-1 \}$. Can this be done? If not manually, then by some efficient algorithm? (Note: Just looping over all values of $i$ is not efficient as $i$ may be very large) Edit: Another way I can think of solving this is by writing both $p$ and $q$ as product of disjoint cycles: $$ p = c_1c_2\ldots c_k \text{ and } q = d_1d_2\ldots d_l $$ And thus, as disjoint cycles commute: $$ p^i = c_1^ic_2^i\ldots c_k^i $$ How to proceed after this?
113901
Prove the following: If $a \mid bc$, then $a  \mid \gcd(a, b)c$.   I tried to set $\gcd(a, b)$ to $b$ and used the fundamental theorem of arithmetic to prove that it is divisible by $a$, but I can't prove that $a \mid bc$, if and only if $a\mid b$ and $a\mid c$. Please help. Thanks.
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!
108006
We were given the following problem as an assignment, we proved the converse in class for prime numbers; however, we can't use the assumption that $\operatorname{gcd}(a,b) = 1$.  So I am struggling to think of my first possible move.  We are given $ar + bs = 1$, the only think I can think of is let $d$ be a common divisor or $ar + bs$ and then show that the $d = 1$.  However, I am not really sure how to do that.  If anyone could just give me a hint or two to nudge me in the right direction I would be appreciative.
11214
Attempted Proof:  Let $S = \{k: n^k-1 \equiv 0 \pmod{p}, k\in \mathbb{N}\}$. Minimal element $r$ exists by Well-Ordering. we show $r=q$.  We note, $\gcd(p,n)=1$, otherwise $p \mid n^q-1 \implies p \mid 1$.  We have:  $n \not\equiv 1 \pmod{p}\implies n^2 \not\equiv n \pmod{p}$ ; [since $p , n$ are coprime and  $p$ prime ]. Now, for any $0&lt;j&lt; i &lt; r,$  $n^i \equiv n^j \pmod{p} \implies n^j(n^{i-j}-1) \equiv 0 \pmod{p} \implies (n^{i-j}-1) \equiv 0 \pmod{p} $, contradicting the minimality of $r$.   Now, we proceed to show that, all elements of $S$ are integral multiples of $r$. (Claim 1)  We have, $n^{tr} \equiv 1 \pmod{p} \implies n^{tr+l} \equiv n^l \pmod{p} $, for $0\leq l &lt;r$. Now, for any two such $l$, say $c$ and $d$, with $d&lt;c$ ,   $n^{tr+c} \equiv n^{tr+d} \pmod{p} \implies n^{tr+d}(n^{c-d}-1) \equiv 0 \pmod{p}$, which again contradicts our assumption that $r$ is the least element of $S$. Hence, Claim 1 is established. But, it implies that $q$ is composite (an impossibility); hence $r$ must be equal to $q$ .   Finally, by Fermat's Little Theorem, we have $n^{p-1} \equiv 1 \pmod{p}$ [ it holds, since $\gcd (p, n) =1$].   Therefore, $p-1$ must be an integral multiple of $q$, i.e. $q \mid p-1$.   PS: I am aware of the duplicates, but I want my solution checked. Thank you.
55597
If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b,a^2+b^2)$ is always equal to either 1 or 2, where $\gcd$ is the greatest common divisor. I haven't really ever solved a problem like this before, so I'd like to get some help. Thanks.
7614
How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$?  By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and $dj= b$ where $d=\gcd(a,b)=1$ this is all the information I have gathered from the question but I dont know how to approach and solve it. Can anyone help explain to me how to arrive at the answer? Thanks!
8243
If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can't find a way to use any of the elemental divisibility and gcd theorems to find them.