# 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,707 questions
Filter by
Sorted by
Tagged with
88 views

### proof: If $a$ and $b$ are coprime if and only if $GCD(a,b)=1$ [closed]

In my college textbook, I came across this theorem: My first problem: Then, according to the fundamental theorem of algebra, $a$ and $b$ can be written unambiguously as the product of prime numbers ...
• 93
231 views

### Interesting NT Question With AP and GCD.

Find the number of prime triplets $(p, q,r)$ such that $p(p + 1), q(q + 1),r(r + 1)$ form a strictly increasing arithmetic progression, where GCD $(r − p, 2p + 1)=1$. What I tried: $r(r+1)-p(p+1)=2d$ ...
• 113
1 vote
96 views

• 926
1 vote
72 views

### Expected number of factors of $LCM(1,…,n)$ (particularly, potentially, when $n=8t$)

I’m trying to prove something regarding $8t$-powersmooth numbers (a $k$-powersmooth number $n$ is one for which all prime powers $p^m$ such that $p^m|n$ are such that $p^m\le k$). Essentially, I have ...
• 1,789
110 views

### $\gcd(\text{multiples}(a,b))= \text{lcm}(a, b)$?

I am exploring whether the following assertion holds true in integral domains: $\gcd(\text{multiples}(a,b))= \text{lcm}(a, b)$. Let us make this formal below. Consider two elements $a$ and $b$ in an ...
• 1,139
21 views

• 722
24 views

### Can we find an explicit formula for $r$ and $s$ as a function of $k$

Define $$g=\gcd(2^{k+3}-1,-2×(2^{k+1}-1)).$$ Then we know that there exist some integers $r$ and $s$ such that $$g=r×(2^{k+3}-1)-(2×s)(2^{k+1}-1).$$ Then my question is: Can we find an explicit ...
• 3,854
42 views

### reverse construction chinese remainder theorem

How can I determine the original number $x\in[pq]$ from its remainders $x_p$ and $x_q$, when it's divided by two relatively prime numbers $p$ and $q$, given that $\gcd(p, q) = 1$? I learned about a ...
81 views

### Closed formula for a $gcd$ [closed]

Le $k≥1$ be positive integer. I am asking if it is possibe to find a closed formula for $$gcd(2^{2k+5}-3×2^{k+2}+1,2×(2^{k+2}-1)(2^{k+1}-1),2×(3×2^{k+1}-1)(2^{k+2}-1))$$ where $gcd$ is the greatest ...
• 3,854
1 vote
38 views

### Least common multiple and greatest common divisor for monomial with rational coefficients

I have read in my textbook that if I have, for example two monomials $A$ e $B$ one or both with rational coefficients, $$A=\frac 34 x^2y^3, \qquad B=-2xyz$$ for the $\text{lcm}$ or the $\text{gcd}$ we ...
• 7,792
1 vote
63 views

### Find the $\gcd(a^{2^m} + 1, a^{2^n} + 1)$ if $m>n$. [duplicate]

From what I know, the question can be solved from congruence modulo or without. Since the question is before the concept of congruence modulo in the book which I am using, I guess a solution without ...
• 49
491 views

• 2,761