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
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?
126
votes
7answers
25k views

Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

For all $a, m, n \in \mathbb{Z}^+$, $$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
28
votes
4answers
5k views

If $a \mid m$ and $(a + 1) \mid m$, prove $a(a + 1) | m$.

Can anyone help me out here? Can't seem to find the right rules of divisibility to show this: If $a \mid m$ and $(a + 1) \mid m$, then $a(a + 1) \mid m$.
4
votes
3answers
1k views

Show $GCD(a_1, a_2, a_3, \ldots , a_n)$ is the least positive integer that can be expressed in the form $a_1x_1+a_2x_2+ \ldots +a_nx_n$

Given $a_1, a_2, a_3, \ldots , a_n$ not all zero, show $\gcd(a_1, a_2, a_3, \ldots , a_n)$ is the least positive integer that can be expressed in the form $a_1x_1+a_2x_2+ \ldots +a_nx_n$. Also deduce $...
30
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 ...
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....
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 ...
7
votes
2answers
8k views

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$.

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ for $0\ne a,b,c\in \Bbb{Z}$. I tried solving it with sets but I sense there are some details I am missing. I would truly appreciate your reference.
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
7answers
22k views

If $\gcd(a,b)= 1$ and $a$ divides $bc$ then $a$ divides $c\ $ [Euclid's Lemma]

Well I thought this is obvious. since $\gcd(a,b)=1$, then we have that $a$ does not divide $b$ AND $a$ divides $bc$. this implies that $a$ divides $c$. done. but apparently this is wrong. help ...
16
votes
7answers
40k views

If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$

How do I go about proving this? If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$. I'm very confused with gcd proofs.
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 ...
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(...
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 ...
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$ ...
8
votes
1answer
621 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 .
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 ...
16
votes
2answers
6k views

$\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ [duplicate]

Possible Duplicate: Number theory proving question? Dear friends, Since $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1, how can we prove that $$ \gcd (b ^ x - 1, b ^ y - 1, b ^ z - 1 ,...
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 ...
5
votes
6answers
535 views

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

I'm having issues figuring out how to approach this problem: Conclude that if $ad-bc = \pm 1$, then $$\gcd(x,y) = \gcd(ax +by, cx + dy)$$ The fact that $\gcd(x,y) = \gcd(x+ky, y)$ is a very ...
4
votes
2answers
870 views

If $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \cdot\gcd(b, c)$

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 $...
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$ ...
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$...
4
votes
3answers
2k views

Smallest positive element of $ \{ax + by: x,y \in \mathbb{Z}\}$ is $\gcd(a,b)$ [duplicate]

Let $S = \{ax + by: x,y \in \mathbb{Z}\}$ and let $e > 0$ be the smallest element in $S$. Prove that $e \mid a$, and hence prove that $e = \gcd(a,b)$ I'm afraid I can't provide much of my initial ...
1
vote
2answers
720 views

Greatest common divisor is the smallest positive number that can be written as $sa+tb$

We know that $d = \gcd(a, b)$ can be written as $sa + tb$, where $s, t \in \mathbb{Z}$. Apparently, $d$ is the smallest positive number that can be written in this form. Why is this so?
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 ...
8
votes
9answers
578 views

Proving $\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$

How would you go about proving that $$\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$$ for any two integers $a$ and $b$? Intuitively it is true because when you divide $a$ and $b$ by $...
1
vote
4answers
249 views

If $m=\operatorname{lcm}(a,b)$ then $\gcd(\frac{m}{a},\frac{m}{b})=1$

Let $a,b\in \mathbb{N}$ and $m=\operatorname{lcm}(a,b)$. Prove that $\gcd(\frac{m}{a},\frac{m}{b})=1$. Any suggestion how to prove I would appreciate. I have try to it directly but I don't get ...
4
votes
4answers
722 views

prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$

I'm trying to prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$ I showed that both $n,m$ divides $nm/\gcd(n,m)$ but I can't prove that it is the smallest number. Any help will be appreciated.
64
votes
8answers
14k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
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 ...
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
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!
13
votes
1answer
879 views

$\text{lcm}(1,2,3,\ldots,n)\geq 2^n$ for $n\geq 7$

I can prove that $\text{lcm}(1,2,3,\ldots,n)\geq 2^{n-1}$. Newly, i read in a paper that for $n\geq 7$ we have: $$\text{lcm}(1,2,3,\ldots,n)\geq 2^n$$ Can you prove it? (This inequality is an ...
9
votes
1answer
2k views

If $\gcd(a,b)=d$, then $\gcd(ac,bc)=cd$?

$A$ an integral domain, $a,b,c\in A$. If $d$ is a greatest common divisor of $a$ and $b$, is it true that $cd$ is a greatest common divisor of $ca$ and $cb$? I know it is true if $A$ is a UFD, but can'...
5
votes
3answers
9k views

Prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$

So, if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$ means $1=ax+by$, and want to show $a^2x+b^2y=1$. By squaring $1=ax+by$ both sides, I get, $1=(ax)^2+b(2axby+by^2)$. It doesn't help my proof. Please help ...
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 ...
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.
2
votes
2answers
308 views

Beginner: How to complete the induction case in a proof that all multiples are a product of the least common multiple

As a disclaimer, I'm fairly new to higher-level mathematics and this is my first question here, so please let me know if I need to clarify anything. I am trying to prove that if I have some natural ...
7
votes
1answer
2k views

Showing $\gcd(2^m-1,2^n+1)=1$

A student of mine has been self-studying some elementary number theory. She came by my office today and asked if I had any hints on how to prove the statement If $m$ is odd then $\gcd(2^m-1,2^n+1)=...
2
votes
4answers
4k views

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. [duplicate]

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from ...
2
votes
3answers
982 views

Prove GCD of polynomials is same when coefficients are in a different field

Prove that the greatest common divisor of two polynomials $f, g$ in $\Bbb Q[X]$ is equal to their greatest common divisor in $\Bbb C[X]$. I am having trouble writing this proof. I tried setting it up ...
2
votes
2answers
608 views

Understanding the Existence and Uniqueness of the GCD

Definitions For $a,b \in \mathbb{Z}$, a positive integer $c$ is said to be a common divisor of $a$ and $b$ if $c\mid a$ and $c\mid b$. $c$ is the greatest common divisor of $a$ and $b$ if it is a ...
1
vote
2answers
5k views

Prove that if d is a common divisor of a and b, then $d=\gcd(a,b)$ if and only if $\gcd(a/d,b/d)=1$ [duplicate]

Prove that if d is a common divisor of a and b, then $d=\gcd(a,b)$ if and only if $\gcd(a/d,b/d)=1$ So far I used what was given so I have $a=dk$, $b=ld$ and $\gcd(a,b)=d$ can be written as a linear ...
-1
votes
2answers
518 views

Prove Order of $x^k = n/{\gcd(k,n)}$ by taking cases

Algebra by Michael Artin Prop 2.4.3 Proposition 2.4.3 Let $x$ be an element of finite order $n$ in a group, and let $k$ be an integer that is written as $k = nq + r$ where $q$ and $r$ are ...
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. ...
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. ...
4
votes
5answers
1k views

Show that $\rm lcm(a,b)=ab \iff gcd(a,b)=1$

Show that $$\rm lcm(a,b)=ab \iff \gcd(a,b)=1.$$ My attempt: If $\gcd(a,b)=1$ then there exist two integers $r$ and $s$ such that $$ar+bs=1.$$ and then I'm stuck... any advice?
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 ...
4
votes
1answer
1k views

Show $(2^m-1,2^n+1)=1$ if $m$ is odd [duplicate]

Let $(2^m-1,2^n+1)=1$ and suppose $m$ is even. Also, $m,n,k\in \mathbb{N}$. We have $$(2^{m}-1)x+(2^n+1)y=1$$ $$(2^{2k}-1)x+(2^n+1)y=1$$ $$(2^{2k}-1)y\equiv 1\pmod{2^n+1}$$ $$(2^k+1)(2^k-1)y\equiv 1\...