# Questions tagged [gcd-and-lcm]

For questions related to gcd (greatest common divisor, also known as the hcf, the highest common factor), lcm (least common multiple), and related concepts from integer and ring theory.

2,605 questions
Filter by
Sorted by
Tagged with
33 views

### How to solve this problem by making a table where vertically you have the multiples of 3, horizontally, you have the multiples of 4 and five, eliminat

How to solve this problem by making a table where vertically you have the multiples of $3$, horizontally, you have the multiples of $4$ and five, then you cross out any sum of the $3m+4n$ or $3m+5k$ ...
41 views

### How do I find a second pair of integers x and y for 200x + 85y = gcd(200,85)? [duplicate]

I understand to use the Euclidean algorithm to find gcd(200,85) and then reverse Euclidean algorithm to find a pair of integers that satisfies gcd(200,85)=200x+85y. My first pair was 200(3) + -7(85)
36 views

35 views

### Calculate GCD of polynomial [duplicate]

I have tried so hard to solve this but I always ended up with $\frac{2}{9}$ but it is 1 GCD $x^5+x+1$, $x^3+2x^2+1$
61 views

### LCM and GCD of numbers with euclidean algorithm.

I know that given two numbers $a$ and $b$ such that $a=bq+r$ then $(a,r)$ and $(a,b)$ are the same. But I want to know if this is true with the LCM as well. I think this is untrue, because if we let ...
30 views

119 views

### Common Roots of Several Multivariate Polynomials with Integer Coefficients with an Additional Property: Their GCD is Linear when Some Variables Fixed

Note: the precise formulation of the problem is at the end of the post. $\def \y {\boldsymbol y} \def \z {\boldsymbol z} \def \a {\boldsymbol a} \def \Z {\mathbb Z}$ Consider a finite set of ...
1 vote
32 views

### Proof that if gcd(a, b) = 1, then lcm(a, b) = ab [duplicate]

I am trying to show the following. If $gcd(a,b) = 1$ then $lcm(a, b)=ab$. I am assuming a and b are positive integers. I have looked at the following questions on here which are using different ... 198 views

### Proving that a non-trivial GCD of strings $a$ and $b$ exists iff $a+b=b+a$

Firstly, assume there are two strings $a$ and $b$. Let the GCD of the two strings is the longest string which divides both. String $t$ divides $s$ iff $s = t + t + \dots + t$. How can I show that a ...
66 views

### Figuring out $\gcd(5a+3,4a+7)$ for $a>0$ [duplicate]
I am having a lot of trouble with a GCD problem. The problem is find $\gcd(5a+3,4a+7)$ for $a>0.$ I have been working on this for quite a while now and have the following issues: I first tried to ...
### Congruence equation $v^q \equiv a \pmod p$
I am reading a text on number theory, but I am confused about the following. Let $a$ be neither $\pm 1$ nor a perfect square. Suppose $h$ is the largest positive integer such that $a$ is a perfect $h$...