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:
Homework Statement
Find the representation of 1 in terms of linear combination of 2003 and 205Homework Equations
The previous questions ask me to find GCD and LCM, which is 1 and 410 615 respectivelyThe Attempt at a Solution
And yes, I don't have any freaking idea to solve this :(
Homework Statement
If (a,c) = 1 and (b,c) = 1, prove that (ab,c) = 1. Note that (x,y) refers to the greatest common divisor between x and y.
2. The attempt at a solution
There is a theorem that says since (a,c) = 1, there exist integers u and v such that au + cv = 1. Likewise, there...
Homework Statement
If two integers a and b are relatively prime and if each divides an integer n, prove that their product ab divides nHomework Equations
1=sa+tb for some integers s and t (thm 1.35)
gcd(a,b)=1
n=aa'=bb'
The Attempt at a Solution
I have tried many many different ways to...
I was doing a couple proofs (since I'm new to them) involving gcds and I just would like you guys to check them to see if I actually proved anything. There are 2 separate problems here.
For both problems, a,b,c are in Z with a and b not both zero.
PROBLEM 1
Homework Statement
Prove...
Homework Statement
If gcd(ab,c) = 1 then gcd(a,c)=1 and gcd(b,c)=1
2. The attempt at a solution
Well, if gcd(ab,c) = 1 we know that
abk + cl = 1 for some integers k and l
not really sure where to go from here... any hints?
Hi everyone, this is not a homework question just a math puzzle I came across.
Let a and b be any two natural numbers. And let (m,n) denote the GCD of m and n as usual. Prove (2^{a}-1,2^{b}-1) = 2^{(a,b)}-1
I'm thinking of double induction on a and b but I'm having trouble with the...
Hi,
I encountered the following formula while reading, can anyone prove this:
lcm(a,b)=gcd(a^{-1},b^{-1})^{-1}
Also, how could one do the gcd for non-integer?
for example we know that lcm(1/3,2/5)=2. then if we use the formula above then lcm(1/3,2/5)=1/gcd(3,5/2). then gcd(3,5/2) should be...
I'm not exactly sure how to prove or disprove this statement. Just by looking at the c, I'd say it's not true, but I'm not sure how to show it either way.
If (a,b) = 1 and (a,c) = 1, then (ac,b) = 1.
http://i111.photobucket.com/albums/n149/camarolt4z28/IMG_20110719_192439-1.jpg?t=1311127377
Homework Statement
prove that p is prime iff for any integer "a" either (a,p)=1 or p divides a
(where (a,p) denotes the gcd of a and p)
Homework Equations
(a,b)= the greatest common factor of a and b
The Attempt at a Solution
I had no trouble with proving the forward direction...
Homework Statement
Using Euclid's algorithm write a program with a function that determines and returns the GCD of two integer arguments.
This is what i wrote, when i print the remainder is zero, How can i get the last remaninder before the zero value? :confused:
Thanks
Homework...
(a,b)=d means d is the GCD of a and b
Question:
Let (a,b)=1
Prove: (a^2,b^2)=1
The hint that we were given is to prove this by contradiction ... but, I have no idea how to go about even starting this proof ... Any and all help would be greatly appreciated!
can we find the value of gcd(x c y , z) easily and very fast using a computer.
where
1. "c" represents "combinations" used in 'permutations and combinations'.
2. x is very very large number (ex: may be of 100 or 1000 numerical digits)
3. y is also large having 2 to 5 digits less than x...
Homework Statement
If ax+by=1, then (a,b)=1.
Homework Equations
The Attempt at a Solution
I am just wondering if this is true. Because I know it is not true if ax+by=c, then (a,b)=c.
Here is a proof I came up with:
Suppose (a,b)=c, c>1.Then c|a and c|b, but then from our...
Homework Statement
Prove that if N=abc+1, then (N,a)=(N,b)=(N,c)=1.
Homework Equations
The Attempt at a Solution
Assume N=abc+1. We must prove (N,a)=(N,b)=(N,c)=1. Proceeding by contradiction, suppose (N,a)=(N,b)=(N,c)=d such that d\not=1 . Then we know, d | N and d | abc. Thus...
Homework Statement
We know that the gcd of two polynomials can be written as
gcd(p(x),q(x))=p(x)m(x) + q(x)n(x) for some n(x) and m(x) in F[x] F a fieldI want to show gcd(n(x),m(x))=1 for a fixed gcd(p(x),q(x))
The Attempt at a Solution
Well, what I tried was to let D(x)=gcd(p(x),q(x))...
Homework Statement
Show that the elements 3 and 2+\sqrt{-5} in \textbf{Z}[\sqrt{-5}] have a greatest common divisor of 1, but the ideal I = (3, 2+\sqrt{-5}) is not the total. Conclude that I is not principle.
Homework Equations
The Attempt at a Solution
I have got as far as...
Hi everybody,
I am having an extremely hard time understanding a specific relationship that originates from the least common multiple of two or more numbers.
According to "Number Theory and Its History" by Oystein Ore, it is not difficult to see that when one writes
lcm(a,b,c) = p*a =...
urgent algebra GCD Proof problem
Homework Statement
let d=gcd(m,n). Prove that d=am+bn, where a,b are integers.
Homework Equations
use of induction and euclidean algorithm.
The Attempt at a Solution
i know when d being a generator and d=am+bn where m,n are generators, then...
Say I have a sequence a(n) = 100 + n^2 with n ranging through the positive integers. I want to find the largest number g(n) such that g(n) = gcd(a(n), a(n+1)).
Let g be a number that divides both a(n) and a(n+1)
g | 100 + n^2 and g | 100 + n^2 + 2n + 1 therefore g | 2n + 1. This means that g...
Hi.
I need to find the GCD of two numbers in Q[sqrt 3]. Let's suppose these two numbers are 12 and 35. How would you go about finding the GCD of those in Q[sqrt 3]?
thanks~
Just a quick theory question. I'd assume it is, but usually the bigger number goes first.
e.g. gcd(10, 5) = 2
but does gcd (5, 10) = 2?
My guess is yes.
Thanks for the help.
Problem: Let R=Q[y] and suppose f,g \in F[x] both have degree 10 with respect to x and degree 6 with respect to y. Suppose h = gcd(f,g) has degree 4 with respect to x and degree 2 with respect to y. Derive an upper bound (as good as possible) on the number of distinct integers i such that...
GCD in PROOF??
Hey everyone,
I'm taking this course called "Number Theory" and am having a lot of difficulty with it. We're currently on "proofs" and i am having some issues.
Last week was my first weeks classes. The first day my professor jumped right into the material without giving...
Homework Statement
Suppose that gcd(a, b) = 1 with a, b > 0, and let x0, y0 be any integer solution to the equation ax + by = c. Find a necessary and sufficient condition, possibly depending on a, b, c, x0, y0 that the equation have a solution with x > 0 and y > 0.
Homework Equations...
Hi,
I've been going through an intro number theory book and trying to prove everything
but I am stuck on this one exercise
it says to show that gcd(M_e,M_f)=M_gcd(e,f) for all positive integers e and f
where M_n=2^n-1.
Is there a simple proof for this?
I see these questions a...
Homework Statement
Let a,b,c be integers. If (b,c)=1, then (a,bc)=(a,b)(a,c)
Homework Equations
This is difficult to answer because some theorems that we haven't proven yet, we can't use.
The Attempt at a Solution
Let g=(a,b) and h=(a,c), g and h are integers.
That means g|a and g|b...
Homework Statement
Let G and H be cyclic groups, with |G| = m and |H| = n. If gcd(m,n) =1, show that G x H is cyclic.
The Attempt at a Solution
Let a = (g,h) in G x H. Then |a| = lcm (|g|,|h|).
Since gcd(m,n)=1, then lcm (m,n) = mn.
Thus lcm (|g|,|h|) = lcm (m,n) = mn.
so <a> = G x...
1. The problem statement, all variables and given/known data
Let a,b, be positive integers, and let d=gcd(a,b) and m=lcm(a,b). Show ZaXZb isomorphic to ZdXZm
Homework Equations
m=lcm(a,b) implies a|m, b|m and if a,b|c then m|c.
d=gcd(a,b) implies d|a, d|b and if c|a and c|b then d|c...
I am *totally* blanking on how to even begin on this one.
I need to prove that the gcd(a,b) | lcm[a,b].
I know that means that a| lcm[a,b] and that b | lcm[a,b]
but I don't really know where to go from there.
I think a small kickstart is all I really need for now. :)
Thanks!
Hi.
Given a field F and the space of polynomials over it, F[x], I was wondering why it is that the monic generator of the ideal generated by any two polynomial f, g from F[x] is exactly the gcd of f and g.
Thank you!
Kriti
Hi, I am doing a phys experiment, and I find myself trying to obtain some pattern of quantization of some measurements, i.e., I'm trying to find a number (double) that divides at least a significant portion of my data, with an arbitrary remainder. Does anyone know of any algorithm that does this...
i have to write the function gcd for c programme.
here's my code:
int gcd(int m, int n)
{
int s,r,x,y;
if (m>=n)
{
r=m-(m/n)*n;
for(x=m,y=n;r!=0;x=y,y=r)
r=x-(x/y)*y;
}
if(n>m)
{
r=n-(n/m)*n;
for(x=n,y=m;r!=0;x=y,y=r)
r=x-(x/y)*y;
}...
I am a beginner programmer in Java. Just started learning the past few weeks.
I'm taking a class and need to create a method that finds the greatest common divisor of two integers. I can assume that both are positive, but I cannot use the Euclidean Algorithm.
I'm sort of lost, but I...
large number!
1. Finding gcd(2^10,10!
Homework Equations
3. I attempted to try the Euclidean algorithm, but it would take forever. Is there a certain number trick?
1.Show gcd(a,b,c) = gcd(a, gcd(b,c))
Homework Equations
3. My attempt is that gcd(a,b,c) can be written as the product of their prime factors. Let's say x is that product. The thing is, I know how to prove this using prime factorization but there has to be another method concerning...
A GCD question- urgent help!
Find the GCD of 24 and 49 in the integers of Q[sqrt(3)], assuming that the GCD is defined. (Note: you need not decompose 24 or 49 into primes in Q[sqrt(3)].
Please teach me . Thank you very much.
I remember this from awhile back but can't seem to find any justification.
Why is the smallest positive linear combination of two numbers necessarily the GCD of the two numbers?
Here is my problem:
Prove or disprove: If gcd(m, n) = d, then the gcd(a, mn) = gcd(a,m) * gcd(a.n)/d.
I can seem to get it started, sort of, but it just does not seem to get anywhere. I know by definition d | m and d | n. Then arbitrary integers x and y can be used such that m = xd and...
Hello everyone,
I have such problem: there are 2 elevators which go only upwards, and stop on only particular floors, each elevator is described by 2 numbers: (a,r) where a is a number of floor on which the elevator starts and r is a number which is a period of elevator's stops. For example, if...
I am a visitor of this beautiful site, my name is Angelo Spina, I would like to resolve the three following problems, in fact after many attempts I have not succeeded in it, for this reason I kindly ask you to give me a help.
PROBLEM 1.
If the equation y² + a p² = 2 x² (where a is a...
I saw someone say this in another thread. Why is it so important? My best guess is that it has something to do with prime factorization, but that's a pretty wild guess.
For a, b, c, d positive integers, and d = a + bc, prove that gcd(b, d) = gcd(a, b).
I don't know about this. I can use the definition of gcd, the diophantine equation of the form as + bt = c and how it relates to the gcd, and the division algorithm theorem.
I know that gcd(a, b) divides d...
Let a, b, and c be positive integers.
I need to prove two items...
1. abc = GCD(a,b,c) * LCM(ab,bc,ac)
2. abc = GCD(ab,ac,bc) * LCM(a,b,c)
where the GCD is the Greatest Common Divisor and the LCM is the Least Common Multiple.
Could I go ahead and say that (a,b,c)=1, that...