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.

Filter by
Sorted by
Tagged with
-1 votes
1 answer
25 views

How to find the GCD(Greatest common Divisor) of the numbers given as algebraic expressions

I am not able to establish that the GCD will not depend upon the value of $n$. Although by taking some initial values of $n$, the GCD is always 1, how do we prove that it is always 1 whatever be the ...
  • 1
1 vote
2 answers
107 views

Find all polynomials $P(x)$ so that $P(x)(x+1)=(x-10)P(x+1)$

Find all polynomials $P(x)$ so that $P(x)(x+1)=(x-10)P(x+1)$. I'm looking for a general solution to the above problem. For instance, say I was trying to find all polynomials $P$ satisfying $(x+1) P(x)...
  • 1,339
0 votes
1 answer
43 views

If $\gcd(a,c)=1$, then $\gcd(ab, cd) = \gcd(b, d)$? [duplicate]

I am trying to see whether that sentence holds. I did this : Let $\gcd(ab, cd) = g$ : $$\exists s, t:\; s(ab) + t(cd) = g$$ Now we have : $$ \begin{cases} s'a + t'c =1\\ s(ab) + t(cd) = g \end{...
-2 votes
0 answers
26 views

I am having trouble proving that d =1

I know that if m, n are integers and (m,n) = 1, then (m+n, m-n) = 1 or 2, however, I am having trouble making proof Problem Statement
3 votes
0 answers
62 views

Find all polynomials p and q with real coefficients so that $p(x)q(x+1)-p(x+1)q(x)=1$ identically

Find all polynomials p and q with real coefficients so that $p(x)q(x+1)-p(x+1)q(x)=1$ identically. Let $R(x)=p(x)q(x+1)-p(x+1)q(x)$. If one can show that both $p$ and $q$ are at most linear, the ...
  • 1,311
0 votes
1 answer
39 views

Smallest remainder using linear combination of two numbers $a$ and $b$.

Given two numbers $a$ and $b$. We need to find all the linear combinations i.e $$ax+by \le N$$ such that $x \geq 0$ and $y \geq 0$. Please notice the non-negative constraint. What is the smallest ...
0 votes
0 answers
19 views

Is set D together with the following operations a Boolean algebra?

D = {1, 2, 3, 4, 6, 8, 12, 24} The question is "Is set D together with the following operations a Boolean algebra?" The operations are as follows. x + y = lcm(x, y) x . y = gcd(x, y) x' = ...
19 votes
1 answer
429 views
+50

Do we have $\sum_{n=1}^{\infty}\frac{\gcd\left(1+n!,1+n^{2}\right)}{n!}\stackrel{?}{=}e$?

I try to find a balanced exercise on it with Desmos. It seems we have: $$\sum_{n=1}^{\infty}\frac{\gcd\left(1+n!,1+n^{2}\right)}{n!}\overset?=e$$ It seems non trivial as you can remark in replacing ...
  • 3,513
-1 votes
0 answers
29 views

Prove that $gcd(a, m_2*m_1)$ = $gcd(a, m_1)$*$gcd(a, m_2)$ if $gcd(m_1, m_2) = 1$ [duplicate]

Suppose that: \begin{split} &a_1 = gcd(a, m_1)\\ &a_2 = gcd(a, m_2)\\ &gcd(m_1, m_2) = 1 \end{split} How to prove that: \begin{split} &gcd(a, m_1*m_2) = a_1 * a_2 = gcd(a, m_1)*gcd(a, ...
0 votes
0 answers
11 views

When finding the LCM of two numbers, why is one number left out of multiplying when it is repeated in the multiples? [duplicate]

For example, the LCM of 10, 24. In factoring the two numbers, there are 4 twos, one 3, and one 5. But, in using compact or exponents to find the LCM, the correct form is 2 cube, multiplied by 3, ...
0 votes
0 answers
45 views

Lowest Common Multiple of polynomials.

Find the lowest common multiple of: $3x^3-7x^2y+5xy^2-y^3$ $x^2y+3xy^2-3x^3-y^3$ $3x^3+5x^2y+xy^2-y^3$ I look at the second expression, and can immediately simplify it to: $3x(y^2-x^2)-y(y^2-x^2) \...
0 votes
1 answer
52 views

Proof related to gcd of three numbers [duplicate]

We want to develop a version of the Euclid-Bézout algorithm for triples of natural numbers. Let $n_1$, $n_2$, $n_3 \in \mathbb{N}$ but not all three zero. We define $\gcd(n_1, n_2, n_3) \in \mathbb{N}$...
  • 1
0 votes
1 answer
61 views

Proving $(ax,bx)=x(a,b)$ using THIS method [duplicate]

This isn't a duplicate! the "duplicate" question doesn't use my method of proof but other methods and I made it clear that I want this method in specific. I want to prove the following claim ...
  • 29
-2 votes
0 answers
39 views

Find integers x, y and z that check for equality $198x + 238y + 512z = gcd(198, 238, 512)$ [duplicate]

I tried to start by solving as follows: $$198x + 238y + 512z = gcd(198, 238, 512)$$ $$gcd(198, 238, 512)=gcd(gcd(198,238),512)=gcd(2,512)=2$$ So, we have: $$198x+238y+512z=2$$ $$198x+238y=2-512z$$ We ...
  • 121
-3 votes
0 answers
40 views

Show that gcd(gcd(a,b),b)=gcd(a,b) [duplicate]

How to prove this equation through the associative property? $$gcd(gcd(a,b),b)=gcd(a,b)$$
  • 121
-3 votes
0 answers
16 views

Prove that $a\mid, if b\mid c$ and if $gcd(a,b)=d$ then $ab\mid cd$ [duplicate]

We want to get to: $ab \mid cd = cd=k(ab)$ Suppose that $a \mid b $ and $c\mid d$. It follows that we have $b=k_1 a$ and $d=k_2 c$ for integers $k_1$,$k_2$. It follows that $$cd=c(k_2 c)=c^2 k_2$$ $$...
  • 121
2 votes
1 answer
95 views

Prove that $P_j(x)$ and $P_k(x)$ are relatively prime for all positive integers $j\neq k$

Let for $n\ge 1, P_n(x)= 1+2x+3x^2+\cdots + nx^{n-1}$. Prove that for any distinct positive integers j and k, $P_j(x)$ and $P_k(x)$ are relatively prime. The above problem is 2014 Putnam A5. ...
  • 1,339
-1 votes
0 answers
17 views

How does one quantitatively find the number of (coprime integer pair) points in a n x n Grid?

Recall the definition of coprime: Two positive integers are said to be coprime if, \begin{equation} \text{gcd}(a_1, a_2) = 1 \end{equation} If I have a 3 x 3 grid for example, how would I find the ...
2 votes
0 answers
28 views

Extended Euclidean algorithm and extended remainder sequence

Consider the rational polynomials $h,f$: $h:=x^8+x^6-3x^4-3x^3+8x^2+3x-5$ $f:=3x^6+5x^4-4x^2-9x+2$ Compute polynomials $r,t \in \mathbb{Q}[x]$ such that $r\equiv tf \mod{h}$ with $\deg r < 4, \deg ...
-1 votes
0 answers
27 views

Prove that $2^{2^n}+1$ and $2^{2^m}+1$ are coprime if $m,n\in\mathbb{N}$ and $m\not=n$ [duplicate]

Prove that $2^{2^n}+1$ and $2^{2^m}+1$ are coprime if $m,n\in\mathbb{N}$ and $m\not=n$ Hi, I have this question for homework. Does anyone have any idea how you would go about solving it? I tried ...
  • 435
-1 votes
1 answer
69 views

Prove that $a \mid bc$ implies $a \mid \gcd(a,b)\times \gcd(a,c)$ [duplicate]

I want to show that $a \mid bc$ implies $a \mid \gcd(a,b)\times \gcd(a,c)$. My answer: since $$ a\mid ac \quad \text{ and } \quad a\mid bc,$$ we get that $a \mid \gcd(ac,bc)$ which implies that $$ a \...
  • 1,337
-3 votes
1 answer
62 views

If $a$ and $b$ are positive integers, and $p$ is prime then $p$ divides $\gcd(a^2,b)$ if and only if p divides $\gcd(a,b^2)$ [duplicate]

I am stuck in the follow problem: State whether the following statement is true or false: If $a$ and $b$ are positive integers, and $p$ is prime then $p$ divides $\gcd(a^2,b)$ if and only if p divides ...
0 votes
0 answers
7 views

Difference between ranges in irreducible equations.

If we had some random gcd of a polynomial problem problem. What is the main difference between properties of $\mathbb Q [x]$ or $\mathbb Z[x]$? What would change if we added something to the ...
0 votes
0 answers
50 views

Is that true that every number greater than a product of relatively prime numbers is a linear combination of those prime numbers? [duplicate]

Is that true that every number greater than a product of relatively prime numbers is a linear combination of those prime numbers? Why would that be a case? A teacher told us in class today that such a ...
  • 309
-1 votes
0 answers
22 views

Proof that recurent sequance of An = |An-2 - An-1|, where every An is natural, from one point will d, d, 0, d, d, 0, ... where $d = gcd(a, b)$ [duplicate]

Initial conditions: Let we have $a_0, a_1 \in \mathbb N. a_2 = |a_0 - a_1|, a_3=|a_1-a_2|, ...$ Proof that exists $n$ from wich the sequance looks like $d, d,0,d,d,0,...$ where $d=gcd(a_0, a_1)$. So ...
-1 votes
0 answers
15 views

Bezout's Lemma and Lowest Common Multiple Property [duplicate]

Don't close this question because no other post answers the questions I have - I just need to ask some questions when I get responses for understanding. Thanks. Let $a,b,m$ be natural numbers. Let $l =...
0 votes
0 answers
61 views

Show that for all integers $n$, $\gcd(n^6 + 3n^2 + n + 4, n^2 + 1) = 1$ [duplicate]

I got hold of the answer but I'm puzzled by two of the lines. Hoping someone can explain why how the solution is derived for the characters in bold. First, let's observe $\gcd(a,b) = 1$ $n^6 + 3n^2 + ...
  • 19
0 votes
1 answer
137 views

On Tony Kuria Kimani's recent preprint in ResearchGate

(Preamble: The method presented here to compute the GCD $g$ is patterned after the method used to compute a similar GCD in this answer to a closely related MSE question.) Let $\sigma(x)=\sigma_1(x)$ ...
1 vote
0 answers
16 views

Factorization by order finding [duplicate]

Let $N$ be a composite integer and consider any $x\le N$. The order of $x$ in $\mathbb Z_N$ is the smallest integer $r$ such that $x^r\equiv 1\text{ mod }N$. If $r$ is even, then $r/2$ is an integer ...
2 votes
0 answers
51 views

Verify proof: Prove that the order of an element in $S_n$ equals the least common multiple of the lengths of the cycles in its cycle decomposition.

I'm practicing for my upcoming Abstract Algebra midterm, and am trying an exercise in the Dummit and Foote Abstract Algebra book. I would like to verify my solution to the following exercise in ...
9 votes
3 answers
161 views

show that $\operatorname{lcm}(n,n+1,\cdots, n+k) = rn{n+k\choose k}$

Let $n,k$ be positive integers. Show that $lcm(n,n+1,\cdots, n+k) = rn{n+k\choose k}$ for some positive integer r. Observe that it suffices to show that $n{n+k\choose k}$ divides the lcm. For a prime ...
  • 1,311
0 votes
2 answers
25 views

gcd as the greatest common factor wrt divisibility partial order relation

Take $60$ and $100$. Their respective divisors lists are: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 1, 2, 4, 5, 10, 20, 25, 50, 100 The common divisors are: 1, 2, 4, 5, 10, 20 According to these ...
  • 234
5 votes
2 answers
184 views

Write the sum $\sum\limits_{a \in \mathbb{N}}\sum\limits_{b \in \mathbb{N}} \frac{(a,b)}{a^sb^t}$ in terms of the Riemann zeta function

I have the following exercise, and I need some help: Write the sum $$\sum\limits_{a \in \mathbb{N}}\sum\limits_{b \in \mathbb{N}} \frac{(a,b)}{a^sb^t}$$ in terms of the Riemann zeta function ($(a,b)$ ...
  • 61
0 votes
1 answer
73 views

Proof-verification request: On the equation $\gcd(n^2,\sigma(n^2))=D(n^2)/s(q^k)$ - Part II

(Preamble: This inquiry is an offshoot of this answer to a closely related question.) In what follows, denote the classical sum of divisors of the positive integer $x$ by $\sigma(x)=\sigma_1(x)$, the ...
0 votes
1 answer
79 views

Let $R=\mathbb Z_2\oplus \mathbb Z_3\oplus \mathbb Z_5$. How many zero divisors are there in $R$?

Let $R=\mathbb Z_2\oplus \mathbb Z_3\oplus \mathbb Z_5$.Then Total number of the zero divisors in $R?$ (A) $15$ (B) $10$ (C) $20$ (D) $22$ Solution We know that $x$ is a unit $\Longleftrightarrow \ ...
  • 3,371
1 vote
0 answers
32 views

Let d=gcd(a,b). Prove that gcd(a/d, b/d)=1 (using Bezout's identity)

I was hoping someone could help look at my attempt at this proof and how I might finish it. By Bezout's identity, can rewrite our given information as... $\gcd(a,b)=d \Longrightarrow ax+by=d$ Dividing ...
1 vote
3 answers
95 views

find the largest number that can't be written as $2008x+2009y+2010 z$

Find the largest number that can't be written as $2008x+2009y+2010 z$, in the following cases: $x,y,z$ are all positive integers. $x,y,z$ are all nonnegative integers. For integers $a_1,\cdots, a_n,$...
  • 1,339
0 votes
1 answer
34 views

$\text{gcd}$ of the coefficients of a comatrix

I am having issues figuring out how to approach this problem: Let $\mathbf F$ be a field. For every matrix $A\in \mathbf F^{n\times n}$, $\textbf{Com}(A)$ is the comatrix of $A$. It is clear for me ...
  • 6,138
-2 votes
1 answer
45 views

if a is not equal to b prove that GCD$(a+\sqrt2*b, \sqrt2+1)=1$

I have this question: given that a and b are rational numbers if a is not equal to b: prove that $(a+b\sqrt2)/(\sqrt2+1)$ is irrational. so I proved that $(a+b\sqrt2)$ is irrational. but I need to ...
  • 63
1 vote
0 answers
78 views

Conjecture on the prime factorisation of the $\operatorname{lcm}(1,\dots,k) \pm 1$, $k \geq 2$

For $k \in \mathbb{N},\, k \geq 2$, define $S(k) := \operatorname{lcm}(2,\dots,k)$. $S$ stands for "superprimorial", as it is a name I've seen come up once before and that I kinda like: it ...
  • 661
5 votes
1 answer
71 views

prove that there exists $a_{n+1} > a_n$ with $(a_1+\cdots + a_{n+1} )| (a_1^2 +\cdots + a_{n+1}^2)$

Let $1 < a_1<a_2<\cdots < a_n$ be an increasing positive sequence of integers. Prove that there exists $a_{n+1} > a_n$ with $(a_1+\cdots + a_{n+1} )| (a_1^2 +\cdots + a_{n+1}^2)$. One ...
  • 1,311
0 votes
0 answers
20 views

Given nonzero integers $a$ and $b$, If $k \gt 0$, then $lcm(ka, kb)= k \times lcm(a, b)$ without using LCM universal property [duplicate]

I have been doing exercises from David M. Burton's book Elementary Number Theory. This is from Problems 2.4 question 10 (b) in the book. Since 10 (c) is asking readers to prove LCM universal property, ...
  • 1
0 votes
0 answers
21 views

Number of sides of a regular polygon using LCM.

I think this may be true, it works for all I’ve checked, but I’m not sure why. I stumbled across it when thinking that there must be a relation between the LCM of the interior angle and 180 degrees. ...
0 votes
1 answer
49 views

Are these valid proofs for the equation $\gcd(n,\sigma(n^2))=\gcd(n^2,\sigma(n^2))$, if $q^k n^2$ is an odd perfect number with special prime $q$?

Let $N = q^k n^2$ be an odd perfect number with special prime $q$ satisfying $q \equiv k \equiv 1 \pmod 4$. It is known that $$i(q)=\gcd(n^2,\sigma(n^2))=\frac{\sigma(n^2)}{q^k}=\frac{n^2}{\sigma(q^k)/...
1 vote
1 answer
48 views

$ax+by=c$ has unique solution for positive integers

Let $a$, $b$ be positive, relative prime integers. Let $c$ be another positive integer such that $a \nmid c$, $b \nmid c$ and $ab − a − b < c < ab$. We want to show that $ax+by=c$ has unique ...
1 vote
1 answer
22 views

Generalising $ab=\text{hcf}(a,b)\text{lcm}(a,b)$

We have that the product of two numbers is equal to the product of their lowest common multiple (LCM) and highest common factor (HCF): $ab=\text{hcf}(a,b)\text{lcm}(a,b)$. The HCF is alternatively ...
  • 3,823
2 votes
1 answer
50 views

How does one find the GCD of three numbers with large exponent values? [duplicate]

I have a problem which is to find the GCD of three numbers, each of which have large exponents: $$ GCD( 2^{300}, 3^{200}, 2^{200})$$ What I have tried: So far, I think there are two main steps here: (...
  • 119
2 votes
3 answers
100 views

Prove there exist infinitely many $n\in\mathbb N$ for any $a,b,c\in\mathbb N$ which are distinct such that $a+n,b+n,c+n$ are pairwise coprime

Homework problem: prove there exist infinitely many $n\in\mathbb N$ for any $a,b,c\in\mathbb N$ which are distinct such that $a+n,b+n,c+n$ are pairwise coprime. First off, I am aware of a similar post ...
  • 435
1 vote
0 answers
39 views

Prove that there exists such a natural number sequence $a_1,a_2,\ldots$, such that $GCD(a_n,2^{a_n}+1)\rightarrow\infty$ when $n\rightarrow\infty$

Homework exercise: prove that there exists such a natural number sequence $a_1,a_2,\ldots$, such that $GCD(a_n,2^{a_n}+1)\rightarrow\infty$ when $n\rightarrow\infty$. First of all I tried to just find ...
  • 435
3 votes
1 answer
185 views

Find all $m\ge 2$ such that $\phi(n,m)\ge (m-n)\phi(1,m)/m$ and $m^2\mid 2022^m+1$

Let $m,n$ be two positive integers such that $n<m$. Define $$\phi(n,m)=|\{n\le k\le m : (k,m)=1\}|$$ Find all $m\ge 2$ such that $$\text{(i)}\quad \frac{\phi(n,m)}{m-n}\ge \frac{\phi(1,m)}{m} \...
  • 3,477

1
2 3 4 5
50