In mathematics, a GCD domain is an integral domain R with the property that any two elements have a greatest common divisor (GCD); i.e., there is a unique minimal principal ideal containing the ideal generated by two given elements. Equivalently, any two elements of R have a least common multiple (LCM).A GCD domain generalizes a unique factorization domain (UFD) to a non-Noetherian setting in the following sense: an integral domain is a UFD if and only if it is a GCD domain satisfying the ascending chain condition on principal ideals (and in particular if it is Noetherian).
GCD domains appear in the following chain of class inclusions:
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...
$$\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...
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$.
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 ε...
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...
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...