Greatest common divisor Definition and 34 Threads

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

How do computers evaluate the gcd of two integers?

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

Are there any real life applications of greates common divisor of two or more integers?

Are there any real life applications of the greatest common divisor of two or more integers?

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