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

34 views

43 views

14 views

### Question involving ratios and Greatest Common Divisors

Consider 6 variables $a,b,c,x,y,z\in\mathbb Z$. We have two ratios, $a:b:c=1:2:3$ and $x:y:z=1:2:3$. We also have that $\gcd(a,x)=2$. What is $\gcd(a+b+c,x+y+z)$? I know that $\gcd(a,x)=2$, which ...
60 views

### How do I find the value of $\operatorname{LCM} (a_1^k,a_2^k, \ldots ,a_n^k) \pmod {m}$?

LCM can be upto or greater than $10^{50}$. $k$ and $m$ are upto $10^9$. My current approach is Finding the LCM . (LCM % m)^k=A. A % m. This is working but takes a long time in finding LCM using GCD. ...
68 views

### Prove that $\gcd(2^{2^{22}}+1,2^{2^{222}}+1)=1$

The great common divisor (gcd) of $2^{2^{22}}+1$ and $2^{{2}^{222}}+1$ is My work, \begin{align} F_{n}-2&= 2^{2^{n}}+1-2 \\ &=(2^{2^{n-1}}+1)(2^{2^{n-2}}+1)(2^{2^{n-2}}-1)\\ &=(2^{2^{m}}+1)...
96 views

### if the lcm is simply the product, then the integers are pairwise prime

I am trying to prove that let $n_1,\ldots,n_k \in \Bbb Z\setminus\{0\}$. then $\gcd(n_i,n_j)=1 \forall i\neq j$ iff $\operatorname{lcm}(n_1,\ldots,n_k)=n_1\cdots n_k$ I can prove "$\Rightarrow$&...
67 views

### LCM relation for $n$ numbers? [closed]

I just want to know: Is $(\operatorname{LCM}(a_1, a_2, a_3, \ldots, a_n))^k = \operatorname{LCM}\left(a_1^k, a_2^k, a_3^k, \ldots, a_n^k\right)$? Here $1 \leq a_i \leq 10^7$ and $1 \leq k \leq 10^9$ ...
38 views

### How $\{am + pn : m, n \in \mathbb{Z}\}=\langle 1 \rangle$?

I don't understand how $\{am + pn : m, n \in \mathbb{Z}\}$ is equal $\langle 1 \rangle$, doesn't $\langle 1 \rangle$ contains all integer of $\mathbb{Z}$? the passage I got it from - Prime ideal ...
96 views

42 views

### Given that $a,b \in \mathbb{Z}$ and are nonzero. Why is it that $\frac{a}{\gcd(a,b)}$ and $\frac{b}{\gcd(a,b)}$ are coprime? [duplicate]

I understand the definition of coprime, which is $\gcd(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}) = 1$ or $x(\frac{a}{\gcd(a,b)}) + y(\frac{b}{\gcd(a,b)}) = 1$. I am pretty sure that I have to use the ...
11 views

### Checking that U(n) is a set that is closed under multiplication modulo n [duplicate]

In Joseph Gallian's Contemporary Abstract Algebra, example 11 of chapter 2, the author leaves it to the reader to check closure for U(n), so I am trying to figure out if my solution is correct, or ...
29 views

### Prove $\gcd (2^n- 1 ;2^m-1) = (2^d-1)$ [duplicate]

Looking for a high school level proof of $\gcd (2^n-1 ; 2^m-1)=(2^d-1)$ Where $d= \gcd(m;n)$
### Prove that the set of all positive integers less than $n$ and relatively prime to n form a group under multiplication modulo n
I came across the problem Prove that the set of all positive integers less than $n$ and relatively prime to n form a group under multiplication modulo n. Proving the associativity of multiplication ...
### Is it true that $HCF(HCF(a,b),c)=HCF(a,HCF(b,c))$
If $a,b,c$ are any three positive integers, Is it true that $HCF(HCF(a,b),c)=HCF(a,HCF(b,c))$ My try: Case $1.$ if atleast one of $a,b,c$ is equal to ONE , then the claim is True. case $2.$ If every ...