# Questions tagged [gcd-and-lcm]

Use for questions related to gcd (greatest common divisor), lcm (least common multiple), and related concepts from integer and ring theory.

2,554 questions
Filter by
Sorted by
Tagged with
17 views

### Let a, b ∈ Z, not both zero. Prove gcd(−a, b) = gcd(a,−b). [closed]

Let a,b ∈ Z, not both zero. Prove gcd(−a, b) = gcd(a,−b).
71 views

### Halving input but not at each step of a process

I am reading about an algorithm that takes as input $2$ integers and does the following to calculate the GCD: If both are even then then shift right (=division by $2$) both numbers and repeat If one ...
57 views

### determine the gcd of $n^3+3n^2-5$ and $n+2$ [duplicate]

Hello I have to determine the gcd of $n^3+3n^2-5$ and $n+2$, but I can’t do it because I know we have to eliminate the $n$. I tried to eliminate $n^3$ but I’m stuck for the rest.
15 views

### Question from Least Common Factor [closed]

What is the Least common factor (LCM) -2 and 2?
26 views

26 views

### Finding GCD of two numbers [duplicate]

Let (a,b) denote the gcd of the numbers a and b. Let $X=((61^{610}+1,61^{671}-1)^{671}+1,(61^{610}+1,61^{671}-1)^{610}-1)$ a) Find $X$mod $10$ b) What is the minimum number of bits required to ...
55 views

55 views

81 views

### $\gcd(3n^2+1, 2n-3)$

I want to show that $\gcd(3n^2+1, 2n-3)$ divides 31 $\forall n\in\mathbb{N}$. I have tried to begin by eliminating the $3n^2$ factor on the left by adding and subtracting multiples and powers of $2n-3$...
113 views

### Gcd of two numbers of the form $x^a-x^b$

Inspired by this question, which noted that for all natural numbers $a>2$, $(2^{15}-2^3)|(a^{15}-a^3)$. My question deals with generalizing this: Let let $a,b$ be integers such that $a>b\geq1$. ...
46 views

### Irreducible polynomial written as $ap + bq$ [duplicate]

I want to know if the following proposition is true or false : Let $p$ and $q$ $\in \mathbb Q[X]$ two polynomials of degree $\geq 1$ and let $g$ $\in \mathbb Q[X]$ an irreducible unitary polynomial, ...
50 views

41 views

### Find the GCD of a polynomial using the extended Euclidean algorithm and express it in the form $a(x)f(x)+b(x)g(x)$ [duplicate]

I am working on a problem that I can not seem to finish. Find the gcd of $f(x)=x^7+1$ and $g(x)=x^6+x^5+x^3+1$, and express it in the form $a(x)f(x)+b(x)g(x)$ using the extended euclidean algorithm. I ...
56 views

### Find numbers from GCD and LCM [duplicate]

two numbers gcd and lcm are respectively 6 and 600. What is the possible pairs of two numbers?
### Prove that $\gcd(a^{2^m}+1,a^{2^n}+1)=\begin{cases} 1,& \text{ if } a\ \text{is even;} \\ 2 & \text{ if } a\ \text{is odd.} \end{cases}$. [duplicate]
Show that if m> n, then $a^{2^n} + 1$ is a divisor of $a^{2^m} -1$. Show that if $a, m, n \in \mathbb Z ^ +$ with $m \neq n$, then \gcd(a^{2^m}+1,a^{2^n}+1)=\begin{cases} 1,& \text{ if } ...