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.

Filter by
Sorted by
Tagged with
4
votes
2answers
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 ...
13
votes
6answers
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$ ...
3
votes
7answers
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 ...
8
votes
1answer
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 .
4
votes
3answers
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 ...
0
votes
1answer
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?
4
votes
2answers
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 ...
13
votes
7answers
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.
4
votes
4answers
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}$. ...
2
votes
6answers
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 ...
11
votes
3answers
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. ...
10
votes
14answers
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 ...
4
votes
8answers
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$...
3
votes
3answers
5k views

Prove the LCM (Least Common Multiple).

$\newcommand{\lcm}{\operatorname{lcm}}$ Let $m,n$ $\in$ $\Bbb N$. The least common multiple ($\lcm$) of $m,n$ is the smallest natural number $x$, such that $m \mid x$ and $n \mid x$. Prove that the $...
0
votes
3answers
735 views

Prove that for any integer $k \ne 0$, $\gcd(k, k+1) = 1$

I'm learning to do proofs, and I'm a bit stuck on this one. The question asks to prove for any positive integer $k \ne 0$, $\gcd(k, k+1) = 1$. First I tried: $\gcd(k,k+1) = 1 = kx + (k+1)y$ : But I ...
16
votes
1answer
11k views

Is greatest common divisor of two numbers really their smallest linear combination?

In a lecture note from MIT on number theory says: Theorem 5. The greatest common divisor of a and b is equal to the smallest positive linear combination of a and b. For example, the greatest ...
5
votes
4answers
7k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to prove it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. $$(f_{n},f_{n+1})=1,\quad ...
7
votes
2answers
4k views

How to prove that $z\gcd(a,b)=\gcd(za,zb)$

I need to prove that $z\gcd(a,b)=\gcd(za,zb)$. I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you please give me some ...
5
votes
5answers
3k views

Prove: If $a\mid m$ and $b\mid m$ and $\gcd(a,b)=1$ then $ab\mid m$

Prove: If $a\mid m$ and $b\mid m$ and $\gcd(a,b)=1$ then $ab\mid m$ I thought that $m=ab$ but I was given a counterexample in a comment below. So all I really know is $m=ax$ and $m=by$ for some $x,y ...
2
votes
6answers
2k views

Proving that $a,n$ and $b, n$ relatively prime implies $ab,n$ relatively prime

Question: Suppose $a,b \in \Bbb N$, $\gcd (a,n) = \gcd(b,n) = 1$. The question is to prove or give a counterexample: $\gcd(ab,n) = 1$. My Work: This is what I have so far (for $\alpha, \beta, \...
10
votes
10answers
4k views

If the sum of positive integers $a$ and $b$ is a prime, their gcd is $1$. Proof?

I feel this is an intuitive result. If, for example, I was working with the prime number $11$, I could split it in the following ways: $\{1, 10\}$, $\{2, 9\}$, $\{3, 8\}$, $\{4, 7\}$, $\{5, 6\}$. ...
2
votes
2answers
266 views

Assuming that $(a, b) = 2$, prove that $(a + b, a − b) = 1$ or $2$

Statement to be proved: Assuming that $(a, b) = 2$, prove that $(a + b, a − b) = 1$ or $2$. I was thinking that $(a,b)=\gcd(a,b)$ and tried to prove the statement above, only to realise that it is ...
16
votes
12answers
15k views

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$ This seems clear, but I don't know how to prove this.. I was trying to show this by induction such that if $a^{n+1}$ = $rs$ and $b^{n+1}$ = $rt$, then $s,t$ ...
1
vote
3answers
2k views

Simple Property of GCD and Modular Arithmetic

I'm stuck on proving a rather elementary property, as I'm not really sure how to start off the approach. Suppose $g^a\equiv 1$ mod $m$ and $g^b\equiv 1$ mod $m$. Does this imply that $g^{\gcd(a,b)}\...
9
votes
4answers
7k views

Prove $\gcd(a+b,a^2+b^2)$ is $1$ or $2$ if $\gcd(a,b) = 1$

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 ...
2
votes
1answer
490 views

If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$. [duplicate]

Edit: The $F$'s are Fibonacci numbers. I need an idea on how to show the following: If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$. I believe that using the fact that $F_{m+n}=...
3
votes
4answers
5k views

GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)

I was curious as to another method of proof for this: Given $a$, $b$, and $x$ are all natural numbers, $\gcd(ax,bx) = x \cdot \gcd(a,b)$ I'm confident I've found the method using a generic common ...
14
votes
6answers
6k views

Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$. I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = gcd(...
31
votes
8answers
14k views

Why $\gcd(qb+r,b)=\gcd(b,r)$?

Given: $a = qb + r$. Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so? Addendum by LePressentiment on 11/29/2013: (in the interest of http://meta.math....
74
votes
4answers
23k views

How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
22
votes
4answers
3k views

Motivation behind the definition of GCD and LCM

According to me, I can find the GCD of two integers (say $a$ and $b$) by finding all the common factors of them, and then finding the maximum of all these common factors. This also justifies the ...
8
votes
4answers
776 views

Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$

Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$. I was thinking among the lines of: Since $a$ and $b$ are coprime numbers, $\gcd(a,b)=1$. Then there exist ...
16
votes
5answers
5k views

How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?

How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. ...
0
votes
3answers
2k views

How to show that $\gcd(ab,n)=1$ if $\gcd(a,n)=\gcd(b,n)=1$?

Let $a,b,n$ be integers such that $\gcd(a,n)=\gcd(b,n)=1$. How to show that $\gcd(ab,n)=1$? In other words, how to show that if two integers $a$ and $b$ each have no non-trivial common divisor with ...
-1
votes
3answers
302 views

Let $a\mid c$ and $b\mid c$ such that $\gcd(a,b)=1$, Show that $ab\mid c$

Let $a\mid c$ and $b\mid c$ such that greatest common divisor (gcd) $\gcd(a,b)=1$, Show that $ab\mid c$.
29
votes
5answers
8k views

Fibonacci modular results $\ F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$

Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...
8
votes
5answers
1k views

Proof that $\gcd(ax+by,cx+dy)=\gcd(x,y)$ if $ad-bc= \pm 1$

I'm having problems with an exercise from Apostol's Introduction to Analytic Number Theory. Given $x$ and $y$, let $m=ax+by$, $n=cx+dy$, where $ad-bc= \pm 1$. Prove that $(m,n)=(x,y)$. I've tried ...
5
votes
3answers
1k views

For integers $a$ and $b$, $ab=\text{lcm}(a,b)\cdot\text{hcf}(a,b)$

I was reading a text book and came across the following: Important Results (This comes immediately after LCM:) If 2 [integers] $a$ and $b$ are given, and their $LCM$ and $HCF$ are $L$ and $H$...
8
votes
2answers
654 views

Is Gauss's lemma valid for polynomials with coefficients in a GCD domain?

Wikipedia's proof of Gauss's lemma requires this theorem: If $(C \mid S\cdot T) \land \lnot \operatorname{invertible}(C)$, $C$ has a non-invertible divisor in common with at least one of $S$ and $T$...
16
votes
6answers
25k views

Prove $\gcd(a+b, a-b) = 1$ or $2\,$ if $\,\gcd(a,b) = 1$

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ holds. I think the first step should look something like this: $d = \gcd(a+b, a-b) = \gcd(...
19
votes
4answers
27k views

What is $\gcd(0,a)$, where $a$ is a positive integer?

I have tried $\gcd(0,8)$ in a lot of online gcd (or hcf) calculators, but some say $\gcd(0,8)=0$, some other gives $\gcd(0,8)=8$ and some others give $\gcd(0,8)=1$. So really which one of these is ...
11
votes
5answers
3k views

Prove that $\gcd(n!+1,(n+1)!+1)=1$

I'd like to solve this one similarly to my previous question: Is this a Valid proof for $(2n+1,3n+1)=1$? I did find a somewhat related post that uses a different method: How to show that $\gcd(n! + 1,...
8
votes
3answers
4k views

Show that if $a \equiv b \pmod n$, $\gcd(a,n)=\gcd(b,n)$

My problem is how to somehow relate the the gcd and congruence. I know that $(a,b) = ax + by$. I also know that $a \equiv b \pmod n$ means $n\mid a-b$. Any hints? Thanks!
1
vote
3answers
5k views

Proving that $\gcd(ac,bc)=|c|\gcd(a,b)$ [duplicate]

Let $a$, $b$ an element of $\mathbb{Z}$ with $a$ and $b$ not both zero and let $c$ be a nonzero integer. Prove that $$(ca,cb) = |c|(a,b)$$
5
votes
2answers
180 views

Prove that $\gcd( a + a', b + b' ) = 1$ if $ab - a'b' = \pm 1$

Prove that $\gcd(a + a', b + b') = 1$ if $ab - a'b' = \pm 1$ My attempt was: Case 1: $ab - a'b' = 1 \implies \gcd(a, b') = 1$ and $\gcd(a', b) = 1$ Then is it sufficient to conclude that $\gcd(a + a'...
7
votes
7answers
8k 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 ...
18
votes
6answers
25k views

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