gcd

  1. M

    GCD a+b

    a,b ∈ Z, we know a+b=60 and GCD(a,b)=12 value for a and b? I started doing this: 12|a -> exists k1∈Z / 12*k1=a 12|b -> exists k2∈Z / 12*k2=b Then, we know that ∀x,y∈Z 12|k1*a+k2*b If we do k1,k2=1 then, 12|a+b -> 12|60 exists k∈Z / 12*k=60 -> k=5 How can I continue? PD: sorry for my english
  2. M

    Find gcd of f and g in F5

    Find the gcd of f = x^2 - x - 2 and g = x^3 - 7x + 6 in \mathbb{F}_5[x], and express it as a linear combination of them. My work: First note that f =(x+1)(x-2) and g = (x+3)(x-1)(x-2). Using the euclidean algorithm, I have that g = (x+1)f + (x+3) and f = x(x+3) + (x+3) = (x+1)(x+3) So the...
  3. Q

    Extended polynomial GCD

    I am understanding how to get a greatest common divisor, I am having trouble finding two polynomials r(x) and s(x) such that gcd=p(x)r(x)+q(x)s(x). I have seen examples, I just need a complete idiots guide.
  4. N

    GCD of two really large numbers

    Let a = 6^M and b = 2^M where M is your student I.D. Number (8 digits long). We were taught to do these questions using the extended euclidean algorithm, and it worked fine for me on previous questions, but these numbers are too large and I can't get the same method to work for it. Is there...
  5. R

    Another GCD problem

    prove that gcd(((a^m)-1)/(a-1));(a-1))=((a-1);m) Help would be really appreciated.
  6. R

    Problem with GCD

    if gcd(n,m) = d then prove that gcd((a^n)-1,(a^m)-1)=(a^d)-1. Help would be very appreciated.
  7. S

    Help with a proof - gcd

    We define a\mathbb{Z}+b\mathbb{Z}=\left \{ au+bv:u,v\in\mathbb{Z} \right \}. I need to prove that a\mathbb{Z}+b\mathbb{Z}=(a,b)\cdot\mathbb{Z}. so, I need to prove a\mathbb{Z}+b\mathbb{Z}\subseteq (a,b)\cdot\mathbb{Z} and a\mathbb{Z}+b\mathbb{Z}\supseteq (a,b)\cdot\mathbb{Z}. One direction is...
  8. S

    GCD proofs

    I need to prove the following: 1. Let a,b,d\in\mathbb{Z} If d|a and d|b, then: d=gcd(a,b) \Leftrightarrow (\frac{a}{d},\frac{b}{d})=1 Here I was able to prove only one direction: d=gcd(a,b) \Rightarrow (\frac{a}{d},\frac{b}{d})=1 Since d=gcd(a,b), there exist s,t\in\mathbb{Z} such that...
  9. S

    GCD and Cauchy sequences of rationals

    Let P be the set of all prime numbers. For any a,b\in \mathbb{Q} with a = \prod_{p\in P}p^{a_p}, a_p \in \mathbb{Z} and b=\prod_{p\in P}p^{b_p}, b_p \in \mathbb{Z}, I will use the standard GCD (a,b) = \prod_{p\in P}p^{\min(a_p,b_p)}. Let a: \mathbb{N} \to \mathbb{Q} be an arbitrary Cauchy...
  10. G

    Number of pairs with give GCD and LCM (proof)

    Hello, I would like a proof for the following algorithm, please. In order to find the number of pairs with a given GCD (greatest common divisor) and LCM (least common multiple), I find the number n of prime factors in LCM/GCD. The number of pairs is equal to 2^n. Example: GCD=2 and LCM=120...
  11. B

    proof about gcd

    I have to prove that if a,b,c\in\mathbb{Z} Show that gcd(a,b)=1$ and $gcd(a,c)=1 iff gcd(a,lcm[b,c])=1 I've tried proving the forward direction and im stuck. Here is what I have so far. proof: \rightarrow: Assume gcd(a,b)=1$ and $gcd(a,c)=1 . Assume further that gcd(a,[b,c])\neq 1 . Let...
  12. K

    Find gcd

    How to find the gcd of f(x)=x2 - x-2 and g(x)= x3-7x+6 in F3[x]. Expressed as a linear combination of f,g.
  13. K

    Eulcidean Algorithim for GCD

    Find the GCD for 198 and 765 I got as far as 765= 3 \times 198 +171 I'm not sure what to do for the next step.
  14. H

    gcd x lcm

    just filling in some gaps in proofs of dm=ab. d=(a,b)=gcd(a,b) m=[a,b]=lcm(a,b) Meserve, Dover a=p1d, b=p2d, (p1,p2)=1…..definition of d p2a=p1b=p1p2d = c, a common multiple. Assume c=rm…. (missing in Meserve) m=q1a=q2b p2a=rq1a → p2=rq1 p1b=rq2b → p1=rq2 r=1 because (p1,p2)=1 → c=m...
  15. U

    question about gcd

    Why gcd(i,p-1)=1 iff gcd(p-i,p-1)=1 ?
  16. M

    Euclidean GCD Algorithm (Proof)

    I'd like to have a formal proof of the following case (case 2) related to the euclidean GCD algorithm: We have M > N, and N > M/2, I'd like to show that M - N > M / 2. Thank you!
  17. P

    Another GCD Proof

    Im new to the forum so im not sure if im posting in the right section but ive been stuck on this problem for days however im not sure on how to even go about it. I would at the very least need some advice on how to tackle this problem. (Headbang) Claim: For every pair of positive natural...
  18. M

    Gcd & lcm

    Studying online work, and have these are 2 problems I cannot complete, , Is anybody able to do these and show work so I can follow along?
  19. S

    GCD Proof

    if I have x and y be odd integers. Then 2gcd(x,y) = gcd(x+y,x-y). I am completely lost for what to do. I may be over think this but help would greatly be appreciated. This is what I have so far: Let d = gcd(x,y) and e = gcd(x+y, x-y). To prove that e = 2d it suffices to show that 2d|e and e|2d...
  20. M

    Greatset Common Divisor (GCD) Questions

    Q1) Are the GCD, Greatest Common Factor (GCF) and Highest Common Factor (HCF) all referring to the same thing? I'm using the GCD to simplify fractions to their lowest terms. To find the GCD I've been using two methods. The first method is doing prime factorization and multiplying the common...