Gcd Definition and 101 Threads

I have a question about a certain fact from the book of Nussbaumer "Fast Fourier Transform and Convolution Algorithms" in the chapter of Number-theoretic transformation. I have quoted the relevant passage once. There it says: This quotation refers to ##q## being a prime number. But then it...

Hello guys, I am able to follow the working...but i needed some clarification. By rounding to the nearest integer...did they mean? ##z=1.2-1.4i## is rounded down to ##z=1-i##? I can see from here they came up with simultaneous equation i.e ##(1-i) + (x+iy) = \dfrac{6}{5} - \dfrac{7i}{5}## to...

suppose you write, clockwise, n numbers (or "units", doesn't matter) in a circle. you then color, clockwise, each k-th number. you do this until you've colored all n numbers, or until you've reached an already colored number. let x be the number of colored numbers. i've figured that if...

Proof: (a) Suppose that gcd(a, b)=1. Let d=gcd(a+b, a-b). By definition of the greatest common divisor, we have that d##\mid##(a+b) and d##\mid##(a-b). This means d##\mid##[(a+b)+(a-b)] and...

Hello, I read something about to which I have a small question of understanding. Before I would like to outline it a little. So we have the primes ##p## and ##q## and we know ##p|x## and ##n = p\cdot q## furthermore it follows that ##p|n## also holds. Now it was said that if ##p|x##, then...

Determine $\textit{gcd}(2^4 \cdot 3^2 \cdot 5 \cdot 7^2,\quad 2 \cdot 3^3 \cdot 7 \cdot 11)$ and $\textit{lcm}(2^3 \cdot 3^2 \cdot 5,\quad 2 \cdot 3^3 \cdot 7 \cdot 11)$ ok the example appeared to have combine the 2 sets on gcd but I am still ? there is no book answer for this:confused:

In Microsoft Excel, if I type in the formula =GCD(113,100) then it gives me the correct answer of 1. However, if I type in =GCD(1.13*100,100), which means the same thing, it tells me 4. What's going on and how can I fix it? Thanks

Homework Statement Do five positive integers exist such that the positive difference between any two is the greatest common divisor of those two numbers? Homework EquationsThe Attempt at a Solution I found four such numbers, ##\{6,8,9,12\}##. I did this in an ad hoc way though without any real...

Do they use the Euclidean Algorithm?

$$\tiny{g1.1.2 \qquad UHW412}$$ \begin{align*}\displaystyle S&=gcd(2^4\cdot3^2\cdot 5\cdot 7^2,2\cdot3^3\cdot 7\cdot 11)\\ &=gcd(35280,4158)\\ W|A&=126\\ \end{align*} ok I tried to find a direct example but the powers and bases are mixed the answer came from W|A just interested in...

Hello! (Wave) We suppose that the integers $x,y,z$ satisfy $x^2+2y^2=z^2$ and $(x,y)=1$ . I want to show that $(x,z)=(y,z)=1$, and that $x$ is odd and $y$ even. I have tried the following: Let $(x,z)=d>1$. Then there exists a prime number $p$ such that $p \mid d$. Since $d \mid x$ and $d \mid...

1. The problem statement, all variables, and given/known data So we need to make a flowchart of GCD 2. Homework Equations The Attempt at a Solution Here my codes but something bothers me, 1-Take two positive integers N and M 2-If N>M go to step 3 3-K=M 4=K=K-1 5-Check, If K=1 go to...

Homework Statement Suppose that m divisions are required to find gcd(a,b). Prove by induction that for m >= 1, a >= F(m+2) and b>= F(m+1) where F(n) is the Fibonacci sequence. Hint: to find gcd(a,b), after the first division the algorithm computes gcd(b,r). Homework Equations Fibonacci...

I have encountered difficulties in solving this question. Your help is greatly appreciated!

Homework Statement For some reason, my book's solution for this problem is given in a very wordy way, rather than in (Pascal-style) pseudo-code (which is what this book usually gives its solutions in). Here is the problem's statement and solution.: PROBLEM STATEMENT: PROBLEM SOLUTION...

Prove, that for all natural numbers, $a$ and $b$, with $b > a$: \[\frac{ab}{(a,b)}+\frac{(a+1)(b+1)}{(a+1,b+1)}\geq \frac{2ab}{\sqrt{b-a}}\] where $(m,n)$ denotes the greatest common divisor of the natural numbers $m$ and $n$.

Find the greatest common divisor of the natural numbers, $a$ and $b$, satisfying: $$\left(1+\sqrt{2}\right)^{2017} = a + b \sqrt{2}.$$

Homework Statement If A is a set of integers and B is a set properly contained in A, does the greatest common denominator of all of the integers in A divide the greatest common denominator of all elements in B? Homework Equations None. The Attempt at a Solution Obviously gcd(A) divides any...

Homework Statement If gcd(f(x),g(x)) = 1 and m,n ∈ ℕ, show that gcd(f(x)^m, g(x)^n) = 1. Homework EquationsThe Attempt at a Solution So I had previously proved this for non-polynomials: gcd(a,b)=1 then gcd(a^n,b^n)=1 Proof: a = p1*p2*...*pn b = p1*p2*...*pm then a^n = p1^n*p2^n*...*pn^n...

this one got me thinking for a while it starts like this: X=6m2+4n2 and Greatest Common Divisor(GCD) of (m,n)=2 what is the greatest EVEN number that must be a factor of X I started this question by thinking what they asked, the gratest number that is a factor of X then I need to calcualte X...

Hello all! I was trying to solve this problem which is supposed to be easy: Traversing Grid | CodeChef I couldn't solve it so I looked at some solutions, they seem to be using the concept of GCD. I am unable to understand why this works, please help. Thanks!

Homework Statement let m|d, n|d and gcd(m,n) = 1. show mn|d Homework Equations gcd(m,n) = d = mx + ny for x and y in integers The Attempt at a Solution d = mr d = ns 1 = mx + ny 1 = (d/r)x + (d/s)y I don't know, a bit lost, just moving stuff around and not making any real progress. Any tips?

Homework Statement If a≡b(mod n) and d=gcd(a.n), prove that d=gcd(b,n).[/B]Homework Equations If a≡b(mod n) → n|(a-b) → a-b =nk, for some k∈ℤ → a=nk+b If d=gcd(a.n) → d=ax+ny gcd(b,n)=d ↔ d|b and d|n, and if c|b and c|n, then c ≤ a. The Attempt at a Solution Since a=nk+b and d=ax+ny, then...

Homework Statement if gcd(a,b) = 1, show that gcd(ac,b) = gcd(c,b) Homework Equations gcd(x,y) = xm + yn for integers n and m The Attempt at a Solution ax + by = 1 gcd(ac,b) = d gcd(c,b) = g ac = dr b = ds c = gm b = gn I've been setting up equations and rearranging things but can't make...

Homework Statement Let a and b be relatively prime. Show that gcd(a+b,ab) = 1 Homework Equations ax+by = 1 for some integers x and y The Attempt at a Solution I set gcd(a+b,ab) = d. I'm now trying to show that d = 1 using elementary algebra techniques. a+b = rd ab = sd ax + by = 1I'm kind...

Homework Statement Show that gcd(a+b,a-b) is either 1 or 2. (hint, show that d|2a and d|2b) Homework Equations d = x(a+b)+y(a-b) The Attempt at a Solution so by the definition of divisibility: a+b = dr a-b = ds adding and subtracting these equalities from each other we can arrive at where...

Homework Statement if 1 = gcd(a,b), show that gcd(ac,b) = gcd(c,b) Homework Equations None The Attempt at a Solution My attempt at a solution: Let d = gcd(ac,b), Let g = gcd(c,b), I want to show that g|d and that d|g. I then went on to make a bunch of circular writing and get nowhere... I...

Problem 1 Suppose ab=cd, where a, b, c d \in N. Prove that a^{2}+b^{2}+c^{2}+d^{2} is composite. Attempt ab=cd suggests that a=xy, b=zt, c=xz. d=yt. xyzt=xzyt. So (xy)^{2}+(zt)^{2}+(xz)^{2}+(yt)^{2}=x^{2}(y^{2}+z^{2})+t^{2}(z^{2}+y^{2})=(x^{2}+t^{2})(z^{2}+y^{2}) Therefore this is...

Homework Statement Give an example of a set S of four (distinct) positive integers such that the greatest common divisor of all six pairs of elements of S is 6. Homework Equations The Attempt at a Solution Can I say that my numbers are in the form? 6 12 18 30 Is this ok?

Homework Statement Consider the following magma, S is not empty; P(S) is the power set. (P(S), U) Now, let A and B be in P(S). What is the GCD of A and B? Homework Equations The Attempt at a Solution If I choose a common divisor of A and B under unions, call it X, I get...

Homework Statement Find the ##gcd(x^3+x^2-x, x^5+x^4+2x^2-x-1) ##and write it as a linear combination. Homework Equations The Attempt at a Solution I know the ##gcd(x^3+x^2-x, x^5+x^4+2x^2-x-1)=1## What I have so far is ##1. x^5+x^4+2x^2-x-1=(x^3+x^2-x)(x^2+1)+(x^2-1)## ##2...

The problem asks to find a generator of the principal ideal <6+7i, 5+3i> in Z[i]. It is my understanding that such a generator must be a greatest common divisor of 6+7i and 5+3i. So, let's call this guy d, we should have d(a+bi)=6+7i and d(c+di)=5+3i. I'm not really sure how to find d. If I...

Let a, k , l , m e Z>1 and let a^k=1 (mod m) and a^l= 1 (mod m). Let d=gcd(k,l) Prove that a^d=1 (mod m). I get already confused at the start: Is it true that k|phi(m) (Lagrange) but k can also be a multiple of the order of a (mod m) and then it can be the other way round. Can anybody clarify...

HelloI am studying the problem given in the attachement. In the solution given, it says "Similarly \( d|\gcd(a,-b) \) ". I could not understand why this is so.thanks

Corollary from book: if d= gcd(a,b), then there exists integers x and y such that ax + by = d. This is not an obvious statement to me. Are there any direct proofs to prove this statement? The book proves this by induction. My proof: Suppose d = gcd(a,b) and a and b are positive integers. a...

Let $K$ be an extension field of a field $F$ and let $p(t),q(t)\in F[t]$. Show that the monic greatest common divisors of $p(t)$ and $q(t)$ in $F[t]$ is same as the monic greatest common divisor of $p(t)$ and $q(t)$ in $K$.

Given that GCD(na,nb) = n * GCD(a,b) for a,b,n ∈ Z+ a) Prove that, if GCD(a,b) = 1 then GCD(a+b, a-b) = 1 or GCD(a+b,a-b) = 2 Hint: Let D = GCD(a+b, a-b), show that D | 2a and D | 2b thus D | GCD(2a,2b) then use the given b) Prove that, if GCD(a,B) = 1, then GCD(2a+b, a+2b) = 1 or GCD(2a+b...

Hello, I wounder if there is more method Then using euclides algoritmen to solve this problem Simplifie/shorten(I Dont know how to say in english) \frac{196707}{250971} and I get GCD=6783 and get the answer \frac{29}{37} is there more method? Is there à method that is a lot more faster Then this...

Let $F$ be any field. Let $p_1,\ldots, p_n\in F[x]$. Assume that $\gcd(p_1,\ldots,p_n)=1$. Show that there is an $n\times n$ matrix over $F[x]$ of determinant $1$ whose first row is $p_1,\ldots,p_n$. When $n=2$ this is easy since then there exist $a_1,a_2\in F[x]$ such that $p_1a_1+p_2a_2=1$...

Homework Statement What is the greatest common divisor and least common multiple of the integers below (answer should be left in exponential form)? 2^{3}, 3^{3}, 5^{1}, 11^{2}, 13^{3} and 2^{1}3^{3}5^{2}7^{4}13^{1}Homework Equations The Attempt at a Solution This is exactly the way the...

Let n be a positive integer and a be a positive divisor of n. Is there any general formula to find the number of positive divisors b of n such that (a,b)=1 ?.

Given two numbers m and n, I need to prove that if a linearly manipulate them I can reduce them to their gcd. example:- 5 and 3. 3+3-5=1 which is their gcd. For that I assumed m as gx and n as gy where g is their gcd and x&y are co-prime. So if I am able to prove that linear combination of...

RESOLVED Homework Statement Let a = 123, b = 321. Compute d = gcd(a,b) and express d as an integer combination of ra + sb.Homework Equations This is a question (3.1, page 70 of Michael Artin's Algebra). For those who do not have the book, this problem is relevant to the section on subgroups...

Homework Statement a_1, a_2, b_1, b_2 are all positive integers greater than one. Given that (a_2-1)/(a_1*a_2-1)=(b_2-1)/(b_1*b_2) Show that GCD(a_2-1,a_1*a_2-1,b_2-1,b_1*b_2)=1 Homework Equations (a_2-1)/(a_1*a_2-1)=(b_2-1)/(b_1*b_2) The Attempt at a Solution If I let...

Let r and s be positive integers. Show that {nr + ms | n,m ε Z} is a subgroup of Z Proof: ---- "SKETCH" ----- Let r , s be positive integers. Consider the set {nr + ms | n,m ε Z}. We wish to show that this set is a subgroup of Z. Closure Let a , b ε {nr + ms | n,m ε...

Since 2 is gcd of 2008 and 8002, I can write 2=2008x+8002y for integers x and y. Is there an algorithm for finding x and y?

Homework Statement Solve in N^2 the following system of equations: 1- gcd(x,y)=7 and Lcm(x,y)=91 2- x+y=24 and Lcm =40 The Attempt at a Solution Let d=gcd(x,y) I said there exists an α and β so that x=dα and y=dβ and gcd(α,β)=1 And after doing some work i reached that α divides αβ=13...

Homework Statement Let K \subseteq L be fields. Let f, g \in K[x] and h a gcd of f and g in L[x]. To show: if h is monic then h \in K[x]. The Attempt at a Solution Assume h is monic. Know that: h = xf + yg for some x, y \in K[x]. So the ideal generated by h, (h) in L[x] equals...

Figured it out nvm

Let n be a natural number, and let S be the set of all natural numbers that divide n. For a, ,b in S, let gcd(a, b) = a /\ b and lcm(a, b) = a \/ b. For each x in S, let x' denote n/x. Do de Morgan's laws hold for this system? (gcd = greatest common divisor, lcm = lowest common...