What is Greatest common divisor: Definition and 34 Discussions
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted
gcd
(
x
,
y
)
{\displaystyle \gcd(x,y)}
. For example, the GCD of 8 and 12 is 4, that is,
gcd
(
8
,
12
)
=
4
{\displaystyle \gcd(8,12)=4}
.In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include greatest common factor (gcf), etc. Historically, other names for the same concept have included greatest common measure.This notion can be extended to polynomials (see Polynomial greatest common divisor) and other commutative rings (see § In commutative rings below).
Proof: Suppose gcd(a, b)=d.
Then we have d##\mid##a and d##\mid##b for some a, b##\in## ##\mathbb{Z}##.
This means a=md and b=nd for some m, n##\in## ##\mathbb{Z}##.
Now we have lcm(a, b)=##\frac{ab}{gcd(a, b)}##...
What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers?
Should you use Euclid’s algorithm in some cases and prime decomposition in others?
What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers?
Should you use Euclid’s algorithm in some cases and prime decomposition in others?
I consider two sequences of numbers $A=\{a_1,...,a_n\}$ and $B=\{k-a_1,...,k-a_n\}$, where $a_1 \le a_2 \le ... \le a_n \le k$.
I am looking for such conditions under which: $gcd(a_1,...,a_n) = gcd(k-a_1,...,k-a_n)=1$.
In more general form: $gcd(a_1,...,a_n) = gcd(k-a_1,...,k-a_n) \ge 1$.
I...
Hi,
I read definition of GCD theorem, from book and from mathWorld website.
"
There are two different statements, each separately known as the greatest common divisor theorem.
This does not make sanse
1. Given positive integers and , it is possible to choose integers and such that ...
Hi,
I need opinion about this problem.
==================================================
question :Prove:
If(a,b)= l and if ( "(a,b)=1" mean greatest common divisor of integers and b is 1 )
c|a (c divides a)
and
d|b (d divides b )
then
(c,d)= 1. ( "(c,d)=1" mean...
NOTE: presume real coefficients
If a pair of polynomials have the Greatest Common Factor (GCF) as 1, it would seem that any root of one of the pair cannot possibly be a root of the other, and vice-versa, since as per the Fundamental Theorem of Algebra, any polynomial can be decomposed into a...
I was reading about Gauss's Lemma here:
https://cims.nyu.edu/~kiryl/Algebra/Section_3.10--Polynomials_Over_The_Rational_Field.pdf
Unfortunately, I am stuck on Lemma 3.10.1 that concludes that the product of a pair of primitive polynomials is itself primitive.
I understand about how there is...
I'll call it the "Wheel Lug Lemma" for now.
If there are a pair of integers p & q such that the Greatest Common Denominator is 1, and there is some number s that is product of p and an increasing whole number n, then the remainder of the division of s by q will cycle through all values of from...
Decide which of the following is true or false. If false, provide a counterexample.
(a) For any integer $n$, $\gcd(n, n+1) = 1$.
(b) For any integer $n$, $\gcd(n, n+2) = 2$.
(c) For any integer $n$, $\gcd(n, n+2) = 1$ or $2$.
(d) For all integers $n, m:$ $\gcd(n, n^2+m) = \gcd(n,m)$.
I...
ok so is there a function that exists (for all intents and purposes let's call it G(x,y) )where
x= a^2*b^4*c
y=a^4*b^2*d
G(x,y) = a^2*b^4
basically gcd, but the exponents match those of the common prime factors of the first input (x)
********
equally useful would be a function where the...
Homework Statement
Find the monic greatest common divisor of two polynomials a = 6x6 + 12x5 - 6x4 -12x +12 and b = 3x4 - 3.
Homework Equations
The Euclidean Algorithm.
The Attempt at a Solution
Applying the Euclidean Algorithm, I have
a = 6x6 + 12x5 - 6x4 -12x +12 = (3x4 - 3)(2x2 + 4x -2)...
Hello! :cool:
I want to find the greatest common divisor of $x^4+1$ and $x^2+x+1$.
I applied the Euclidean division and found that $x^4+1=(x^2+x+1) \cdot (x^2-x)+(x+1)$.
So,isn't it like that: $gcd(x^4+1,x^2+x+1)=x+1$ ?
But.. in my textbook,the result is $1$! Which of the both results is...
can I get hints on how to prove this question:
let a,b be in Z(integer) with h=gcd(a,b) not equal to zero then [(a divide b), (b divide h)] are in Z. and gcd[ (a divide h, b divide h)]=1
Hey! :o
The greatest common divisor of $a$ and $b$ can be written as a linear combination of $a$ and $b$.
Let the set $D=\{xa+yb|x,y \in Z\}$.
a) $D$ contains non-zero elements.
b) $D$ contains also positive numbers.
c) The set of positive numbers of $D$ (let $D^+$) is $ \neq \varnothing$...
I am working on Exercise 8 of Dummit and Foote Section 9.2 Exercise 8
====================================================================================
Determine the greatest common divisor of a(x) = x^3 - 2 and b(x) = x + 1 in \mathbb{Q} [x]
and write it as a linear...
Homework Statement
The problem went "If c|a and c|b then c|gcd(a,b) where cεN and a,bεZ"
Homework Equations
The Attempt at a Solution
My proof went like this " Let a=cr and b=cs where r,sεZ. We want to show c|gcd(a,b). Lets
start with cd=ax+by where d,x,yεZ since the gcd(a,b) can...
Homework Statement
define the gcd of a set of n integers, S={a_1...a_n}
Prove that exists and can be written as
q_1 a_1+...+q_n a_n for some integers, q_1...q_n
Homework Equations
Euclid's Algorithm?
The Attempt at a Solution
I have the statement that gcd(a_1...a_n) = min( gcd(a_i, a_j)...
Homework Statement
prove that: x^y=(5x+3y)^(13x+8y)
Homework Equations
The Attempt at a Solution
Can I say that x^y divides both 5x+3y and 13x+8y and go on from there or what?
Then in case one u could multiply 5x+3y by 13 and 13x+8y by 5 and do the difference and you'll get that x^y divides...
Homework Statement
Suppose a, b ∈ N and a|b. Prove that a = gcd(a, b).
Homework Equations
Seems easy intuitively but actually proving it is giving me problems.
The Attempt at a Solution
I have been trying to use the fact that gcd(a,b)=na + mb here m and n are integeres but got stuck.
Homework Statement
I need to show that two elements in \textbf{Z}[\sqrt{-5}] have gcd = 1.
The elements are 3 and 2+\sqrt{-5}
Homework Equations
The Attempt at a Solution
My way of thinking was if I can show that both elements are irreducible, then they are both prime and hence...
Homework Statement
Don't have the book with me, but the problem basically asked me to prove that
gcd(a,b)=1 \Rightarrow gcd(an,bn)=n
Homework Equations
Since gcd(a,b)=1 is a fancy way of saying a and b are relatively prime (or is "a and b are relatively prime" a fancy way of...
Homework Statement
(1). If gcd(a,b) = d , gcd(a/d,b/d)=1
(2). If gcd(a,b) = d , then gcd(m,n) = 1 , where dm=a, dn=b
(i don't know wether this statement is correct)
Homework Equations
n/a
The Attempt at a Solution
i kow how to prove (1) and (2), but i only proof (2) using...
Homework Statement
(b) Suppose a certain student’s ID number M satisfies
gcd(M, 2010) > gcd(M, 271) > 1.
Find all possible values for gcd(M, 2010). Be sure to explain your reasoning. [Note:
both 271 and 67 are prime.]
(c) Suppose that the ID number...
Claim: n! + 1 and (n+1)! + 1 are relatively prime.
How can we prove this? Can we use mathematical induction?
Base case: (n=1)
gcd(2,3)=1
Therefore, the statement is true for n=1.
Assuming the statement is true for n=k: gcd(k! + 1,(k+1)! + 1)=1 (induction hypothesis), we need to show...
If there are integers s,t with as+bt=6, this implies that gcd(a,b)=6, right?
And if gcd(a,b)=6, does this necessarily mean that a and b are not relatively prime since their gcd is not 1? (I have read that two integers a and b are relatively prime if gcd(a,b)=1).
Homework Statement
if (a,c)=1 and (b,c)=1 prove that (ab,c)=1
Homework Equations
I know that (a,c)=1 says that au+cv=1 and bs+ct=1 prove abq+cr=1
The Attempt at a Solution
I set au+cv=bs+ct now I don't know what to do
Homework Statement
Given gcd(a,b)=1, what is the gcd(a^2+b^2, a+b) where ^=square.
Homework Equations
The Attempt at a Solution
gcd(a^2+b^2, a+b) = gcd ( (a+b)^2 -2ab, a+b) which i think, we can reduce to gcd(2ab, a+b). Here is where I stucked. I am not sure how to proceed. Please...
Is it possible to calculate the greatest common divisor of decimals and fractions? As far as I know, the greatest common divisor is a number you can calculate for integers, but I wonder if it's possible to calculate it for decimals and fractions.
HI there,
I have a tiny question concerning the gcd of polynomials. Assume, \chi is the greatest common divisor of the polynomails p_{ij}, i,j=1,2. I then form
q_{11}=p_{11}^2+p_{12}^2,\quadd q_{12}=p_{11}p_{21}+p_{12}p_{22},\quadd q_{21}=p_{21}p_{11}+p_{22}p_{12},\quadd...
Homework Statement
Suppsoe a, b\innatural numbers, and d=GCD(a,b). Then d^2=GCD(a^2,b^2). I need to find where the proof goes wrong.
Homework Equations
The Attempt at a Solution
By hypothesis, we have that d divides a and d divides b, so there are integres s and t with a=ds and...