# Questions tagged [gcd-and-lcm]

The concepts of *greatest common divisor* (which is also known as *Highest Common Factor*) and *least common multiple* are closely related notions in the integers, and also make sense in certain other rings. The tag is intended to encompass all questions related to these notions.

1,957 questions
Filter by
Sorted by
Tagged with
3k views

### Bezout's identity in $F[x]$

Let $F$ be a field and $F[x]$ a polynomial ring. Let $p(x)$ be an irreducible polynomial. Show that $\gcd(p(x),q(x)) = 1\Longrightarrow \exists r(x),s(x)$ such that $r(x)p(x)+s(x)q(x) = 1$. I know ...
8k views

### Concise proof that every common divisor divides GCD without Bezout's identity?

In the integers, it follows almost immediately from the division theorem and the fact that $a | x,y \implies a | ux + vy$ for any $u, v \in \mathbb{Z}$ that the least common multiple of $a$ and $b$ ...
500 views

### Proving that $\gcd(5^{98} + 3, \; 5^{99} + 1) = 14$

Prove that $\gcd(5^{98} + 3, \; 5^{99} + 1) = 14$. I know that for proving the $\gcd(a,b) = c$ you need to prove $c|a$ and $c|b$ $c$ is the greatest number that divides $a$ and $b$ Number 2 is ...
622 views

### $\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1$, or $p$

Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$ Thanks in advance .
3k views

### Prove: $a\equiv b\pmod{n} \implies \gcd(a,n)=\gcd(b,n)$ [duplicate]

Proof: If $a\equiv b\pmod{n}$, then $n$ divides $a-b$. So $a-b=ni$ for some integer $i$. Then, $b=ni-a$. Since $\gcd(a,n)$ divides both $a$ and $n$, it also divides $b$. Similarly, $a=ni+b$, and since ...
225 views

### Prove that for every natural number $n$ we have $\gcd(n! + 1, (n + 1)! + 1) = 1$ [duplicate]

I know that we are gonna need to use one of the identities that the $\gcd$ is equal to but I can't remember one that would be useful for this problem. Any help?
10k views

### Proof of Bezout's Lemma using Euclid's Algorithm backwards

I've seen it said that you can prove Bezout's Identity using Euclid's algorithm backwards, but I've searched google and cannot find such a proof anywhere. I found another proof which looks simple but ...
2k views

### How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$

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.
208 views

### Let $m \in \mathbb{Z^+} , n \in \mathbb{Z^+}$ and let $d=\gcd(m,n)$. Prove that $m\mathbb{Z}+n\mathbb{Z}=d\mathbb{Z}$

Let $m \in \mathbb{Z^+} , n \in \mathbb{Z^+}$ and let $d=\gcd(m,n)$. Prove that $$m\mathbb{Z}+n\mathbb{Z}=d\mathbb{Z}.$$ My attempt is use inclusion to show. Let $a \in m\mathbb{Z}+n\mathbb{Z}$. ...
9k views

### Prove that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $\gcd(ab,c)=1$ [duplicate]

Prove that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $\gcd(ab,c)=1$. My attempt is let $\gcd(ab,c)=d$. Since $d \mid ab$ and $d \mid c$ , $d \mid (abt+cs)$ for some integers $s$ and $t$. Then by ...
11k views

### If a and b are relatively prime and ab is a square, then a and b are squares.

If $a$ and $b$ are two relatively prime positive integers such that $ab$ is a square, then $a$ and $b$ are squares. I need to prove this statement, so I would like someone to critique my proof. ...
6k views

### If $(a,b)=1$ then prove $(a+b, ab)=1$.

Let $a$ and $b$ be two integers such that $\left(a,b\right) = 1$. Prove that $\left(a+b, ab\right) = 1$. $(a,b)=1$ means $a$ and $b$ have no prime factors in common $ab$ is simply the product of ...
4k views

### If $\gcd(a,b)=1$, then $\gcd(a+b,a^2 -ab+b^2)=1$ or $3$.

Hint: $a^2 -ab +b^2 = (a+b)^2 -3ab.$ I know we can say that there exists an $x,y$ such that $ax + by = 1$. So in this case, $(a+b)x + ((a+b)^2 -3ab)y =1.$ I thought setting $x = (a+b)$ and $y = -1$...
5k views

### Prove: $\gcd(a,b) = \gcd(a, b + at)$. [duplicate]
I know that $\gcd(a,b)$ divides $a$ and $b$, and must also then divide $(a)(t)$ ($t$ being some integer). This makes sense to me, but how do I prove it? It seems that the addition of $(a)(t)$ is a ...
### Prove that if $\gcd( a, b ) = 1$ then $\gcd( ac, b ) = \gcd( c, b )$
I know it might be too easy for you guys here. I'm practicing some problems in the textbook, but this one really drove me crazy. From $\gcd( a, b ) = 1$, I have $ax + by = 1$, where should I go from ...