Gcd Definition and 101 Threads

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

Show that if a,b\in\mathbb{N}^+,\ \gcd(a,b) = 1 and p is an odd prime, then \gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)\in \{1,p\}

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.

For the first part of this question: So if everything was done correctly is -55/16 my answer?

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

Would the GCD of x^2+x+c and (x-a)^2+(x-a)+c always be 1?

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!

Is there a formula for gcd(a+h,b+k) given gcd(a,b) and gcd(h,k)?...jus wondering

Can anyone help me with this? If gcd(r,s)=1 then prove that gcd(r^2-s^2, r^2+s^2)=1 or 2. i'm so confused.

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

1. If d|ab and gcd(a,b)=1, prove that d=d1d2 where d1|a and d2|b and gcd(d1,d2) = 1 Homework Equations 3. Let d1 = gcd(d,a). Thats all I know

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

What does the notation gcd(x,y) means?

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