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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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$ ...
jkj's user avatar
  • 11
0 votes
0 answers
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)
Cade Martin's user avatar
0 votes
0 answers
36 views

proof: if $a=bq+r$, then GCD ($a,b$) $=$ GCD($b,r$). [duplicate]

Theorem: If $a$ and $b$ are any integers not both zero, and if $q$ and $r$ are any integers such that $a = bq + r$, then GCD($a, b$) $=$ GCD($b, r$). Proof: Suppose $a$ and $b$ are integers, with $...
Omar's user avatar
  • 93
1 vote
2 answers
82 views

Find the greatest common divisor of $ \frac {12\gcd(a,b)}{d}$ and $\frac cd $ [duplicate]

Given that the greatest common divisor of $a$, $b$ and $c$ is $d$. And 3 doesn't divide $\frac cd$, $\frac cd$ is an even integer, $\frac {c}{2d}$ is an odd integer. Find the greatest common divisor ...
Nicholas Gray's user avatar
1 vote
0 answers
41 views

Do all of these partial sums of roots of unity have real part = $\frac{1}{2}$ except at powers of $2$?

Let the Dirichlet inverse of the Euler totient function be: $$\vartheta(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$ and compute the sum: $$q(x,n)=\sum _{h=0}^{\infty } \left(\sum _{k=1}^n x^{h n+k}...
Mats Granvik's user avatar
  • 7,286
1 vote
0 answers
56 views

Show that $a(\gcd (n,k))$ is generated from roots of generating function of $\sum _{h=0}^{\infty } \left(\sum _{k=1}^n x^{h n+k} a(\gcd (n,k))\right)$

Let $a(n)$ be the Dirichlet inverse of the Euler totient function: $$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$ And let the matrix $T$ be: $$T(n,k)=a(\gcd(n,k)) \tag{2}$$ Compute the ordinary ...
Mats Granvik's user avatar
  • 7,286
0 votes
0 answers
50 views

Proof: Suppose $a,b \in \mathbb{N}$. Then a = gcd(a,b) iff $a|b$. [duplicate]

So I've constructed a proof for this answer and I'm having trouble completeing it. To prove iff statements we need to prove the statment $P \rightarrow Q$ then $Q \rightarrow P$. Convert the statement ...
Ziggy's user avatar
  • 147
0 votes
1 answer
29 views

System of equations involving lcm [duplicate]

Given a system: $$ \begin{cases} 5x - 3y = 0 \\ \text{lcm}(x, y) = 45 \end{cases} $$ Since, $5x=3y$, I've tried expressing product of $xy$ as: $$ \text{lcm}(x,y)\gcd(x,y)=xy \\ \gcd(x,y)=\frac{xy}{\...
Felix's user avatar
  • 3
-2 votes
2 answers
71 views

Prove ${\gcd\left({\rm lcm}\left(m_1,m_2\right),m_3\right){\rm lcm}\left(m_1,m_2,m_3\right)} = {\rm lcm}(m_1,m_2)m_3$ [duplicate]

Is it possible to proof: when $gcd\left(m_1,m_2,m_3\right)=1$, then $\frac{lcm\left(m_1,m_2\right)m_3}{gcd\left(lcm\left(m_1,m_2\right),m_3\right)}=\frac{lcm\left(m_1,m_2,m_3\right)}{gcd\left(m_1,m_2,...
xMath's user avatar
  • 107
-2 votes
0 answers
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$
Taoufik El Afya's user avatar
0 votes
0 answers
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 ...
WEI MINGCHEN's user avatar
0 votes
0 answers
30 views

Question between the proof of divisibility properties of binomial coefficient

I was reading this paper by Erdos in which he derives that there exists infinitely many $n$ such that for any primes $p,q $ where each prime is greater than $2$ $$\text{gcd}\left(\binom{2n}{n},pq\...
RAHUL 's user avatar
  • 1,463
0 votes
0 answers
53 views

Why can we use $\le$ and $\mid$ equivalently in the definition of $gcd$? Can we generalize it to set that have $2$ partial orders available?

The greatest common divisor of two numbers (not both equal to $0$) is defined in $\mathbb N^*$ as the greatest element of the set of common divisors of these two numbers, with respect to the partial ...
niobium's user avatar
  • 969
-2 votes
1 answer
79 views

If $10|abc$, prove that either $10|ab$, $10|bc$, or $10|ac$. [closed]

Given three integers $a$, $b$, and $c$ how do I prove that if $10|abc$, it follows that either $10|ab$, $10|bc$, or $10|ac$? I do not get much further than writing out $abc=10\cdot r$, where $r$ is ...
jessegerritsen's user avatar
0 votes
2 answers
73 views

The LCM of three positive integers $X, Y$ and $Z$ is $119^2$. Find the number of ordered triplets $(X, Y, Z)$

The LCM of three positive integers $X, Y$ and $Z$ is $119^2$. Find the number of ordered triplets $(X, Y, Z)$. My question is similar to: What is the number of ordered triplets $(x, y, z)$ such ...
Vasu Gupta's user avatar
2 votes
1 answer
123 views

GCD of Polynomial Roots. [duplicate]

I am sure there is an obvious answer, but suppose I have a monic polynomial with non-zero, integer coefficients given by $$P(x) = x^n + a_{n - 1}x^{n - 1} + \cdots + a_1x + a_0$$ Veita's Formulas ...
jmath's user avatar
  • 123
0 votes
0 answers
20 views

Notation for taking the GCD of values in a vector

Is there any notation to take the GCD of two values in a vector? For example, if I have the following vector $$\left[\begin{eqnarray}10\\8\end{eqnarray}\right]$$ is there a function that can be ...
M1n3c4rt's user avatar
0 votes
0 answers
41 views

Computing the least common multiple of the numbers 1 through n for incremental n

I notice a pattern when computing the least common multiple for the numbers 1 through n as we incrementally increase n. The pattern is that the list of factors does ...
efthimio's user avatar
  • 155
-1 votes
1 answer
75 views

If we know $\gcd(a,b,c)=1$, does it mean $\gcd\left(\frac{a}{\gcd\left(a,b\right)},\gcd\left(c,\frac{b}{\gcd\left(a,b\right)}\right)\right)=1$ [duplicate]

If we know $gcd(a,b,c)=1$, how to prove that $gcd\left(\frac{a}{gcd\left(a,b\right)},gcd\left(c,\frac{b}{gcd\left(a,b\right)}\right)\right)=1$? Where $a, b, c$ are any positive integers. I have test ...
xMath's user avatar
  • 107
2 votes
1 answer
94 views

Finding the GCD in a function

I am currently stuck on a number theory problem. The question is to determine the GCD of every number in the form $p^6-7p^2+6$, where $p$ is a prime number and greater than or equal to $11$. My ...
Enkt Enktson's user avatar
0 votes
0 answers
27 views

if $(a-b)x=km$ ,why does $m$ divide $(a-b)$ if $x$ and $m$ are relatively prime? [duplicate]

I am reading the following proof of this proposition: Let $m, x$ be positive integers such that $\gcd(m, x) = 1.$ Then $x$ has a multiplicative inverse modulo $m$, and it is unique (modulo $m$). There ...
Shmuel's user avatar
  • 1,701
4 votes
2 answers
150 views

Lower bound for greatest LCM

Let $k>1$ be an integer. I am looking to prove or disprove the following conjecture $(\mathscr{C}_k)$ : There exists a constant $C_k>0$ such that for any integer $n\geq k$, if $a_1,\cdots,a_n$ ...
uvdose's user avatar
  • 107
-1 votes
1 answer
28 views

How do I prove that $\gcd(a,b)=\gcd(-a,b)$ [duplicate]

How do I prove that $\gcd(a,b)=\gcd(-a,b)$? Here is what I have tried: Let $d=\gcd(a,b)$ and $d'=\gcd(-a,b)$ Then $d|a$, $d|b$, $d'|(-a)$, $d'|b$ $\implies d'|(b-a)$ and $d|(a+b)$. Then there is some ...
Jason Xu's user avatar
  • 387
2 votes
0 answers
45 views

On generating certain quadruples

As part of running simulations related to this question, I had to write a program that generates quadruples $(\alpha, \beta, a, b)$ such that $\alpha, \beta, a, b$ are all less than $n$ and $\gcd(\...
vvg's user avatar
  • 3,133
2 votes
0 answers
117 views

Some conjectures based on surprising observations on magic squares

Let us restrict ourselves to odd magic squares constructed using the Uniform Step Method of Lehmer (See [Apostol51] for the construction technique). A magic square constructed using Lehmer’s Uniform ...
vvg's user avatar
  • 3,133
1 vote
0 answers
43 views

Relation between Diophantine equations involving multiple sums with the modulo function and greatest common divisor function.

This one of my questions that I have as I am trying to learn about Diophantine equations, and about what I found through an OEIS search here: https://oeis.org/A360323 To generalize: Let the function $...
Mats Granvik's user avatar
  • 7,286
1 vote
1 answer
87 views

Show that these ratios have numerators $\frac{1}{2} \vartheta(n) (-\exp (\Lambda (n)))$ and denominators $\exp (\Lambda (n))$ for $x=1$,

Let the Dirichlet inverse of the Euler totient function be: $$\vartheta(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$ and compute the sum: $$q(x,n)=\sum _{h=0}^{\infty } \left(\sum _{k=1}^n x^{h n+k}...
Mats Granvik's user avatar
  • 7,286
0 votes
1 answer
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 ...
Mohsen Shahriari's user avatar
1 vote
0 answers
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 ...
user avatar
4 votes
3 answers
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 ...
user129393192's user avatar
0 votes
1 answer
66 views

Polynomials GCD over finite field [duplicate]

I'm trying to find the GCD of $x^3+2x^2+3x+4$ and $x+2$ over $\Bbb Z _5[x]$ I tried to use GCD euclidean algorithm and got the folowing: $x^3+2x^2+3x+4 = (x^2+3)(x+2)+3$ $(x+2) = (2x)3+2$ $3=3\cdot2 + ...
3xhaust's user avatar
  • 149
0 votes
1 answer
39 views

Need help with number theory problem involving LCM. [duplicate]

Country A has elections every 4 years with its first election in 1997. Country B has elections every 5 years with its first election in 1994. When would be the first time that both the countries will ...
user avatar
-1 votes
2 answers
53 views

Show that $lcm$ is associative via nesting the maximum-function [duplicate]

I found some proofs for the claim that for natural numbers $a,b,c$ it holds that $$ \operatorname{lcm}(\operatorname{lcm}(a,b),c) = \operatorname{lcm}(a,\operatorname{lcm}(b,c)). $$ I wonder whether ...
mathquester's user avatar
1 vote
0 answers
46 views

Proving a special case of Bézout’s Identity

I’m trying to prove the following. Lemma. Let $a,b,c$ be odd integers with $a>b>c\ge 1$. Then there exist positive integers $u$ and $v$ of opposite parity such that $a=bu-cv$. In particular, a ...
Kieren MacMillan's user avatar
1 vote
2 answers
40 views

gcd(a S)= a gcd(S) (integral domain or ufd) [duplicate]

Les $A$ be an integral domain[1] and $S\subset A$. The set $gcd(S)$ is the set of elements $\delta$ satisfying the two following properties : $\delta|s$ for all $s\in S$ if $d|s$ for all $s\in S$, ...
Laurent Claessens's user avatar
0 votes
0 answers
33 views

Is there a simplification of the expression $\gcd\left(a y(p-q)-x(b-p q),y(a-pq)+x(p-q)\right)$?

Following the question gcd simplification, I was trying to see if $$\gcd\left(a y(p-q)-x(a-p q),y(a-pq)+x(p-q)\right)$$ with $\gcd(x,y)=1$ can be simplified. I tried to eliminate the variable $q$ and ...
John Bull's user avatar
0 votes
0 answers
28 views

Some advices with simple number theory [duplicate]

Given $x$ and $y$, let $m=ax+by$ and $n=cx+dy$, where $ad-bc=\pm1$. Prove that $(m,n)=(x,y)$. First attempt Given that $(x,y)\mid m$ and $(x,y)\mid n$ so $(x,y)\mid (m,n)$. Furthermore, from the ...
yngabl's user avatar
  • 1,014
0 votes
1 answer
66 views

Is the sequence $p_n-n+1$ related to the Goldbach conjecture via the Dirichlet inverse of of the Euler totient?

I am trying to learn what the Goldbach conjecture is and I therefore ran this Mathematica program where I tried to incorporate the conjecture: ...
Mats Granvik's user avatar
  • 7,286
0 votes
0 answers
61 views

Integral affine functions without common factors

Let $f_1$, $\ldots$, $f_m \colon \mathbb{Z}^n \to \mathbb{Z}$ affine functions ( an affine function $f$ is of the form $f(x_1, \ldots, x_n) = \sum_{j=1}^n a_j x_j + b $, with $a_j$, $b \in \mathbb{Z}$)...
orangeskid's user avatar
  • 53.3k
0 votes
0 answers
24 views

Generalization of Bezout's lemma by induction [duplicate]

After proving the $n=2$ case, a lecturer I'm watching stated the generalization of Bezout's lemma and left the induction as an exercise. I think I can see how to prove it without induction, but with ...
Brad G.'s user avatar
  • 2,206
1 vote
0 answers
37 views

Is it possible to eliminate $q$ from $\gcd\left(a (e-gq),(q^2-d)g-(e-gq)(q-p)\right)$?

Is it possible to eliminate the variable $q$ from the following gcd expression? $$\gcd\left(a (e-gq),(q^2-d)g+(e-gq)(q-p)\right)$$ What I tried was the following: Assuming that the gcd is $m$, I get $$...
John Bull's user avatar
1 vote
0 answers
63 views

A special form of Bezout lemma

Let $a_1, a_2, ..., a_n$ be natural numbers and $d$ the gcd of all of them. Using Bezout lemma in number theory we can find integers $k_1, k_2,..., k_n$ such that $a_1k_1 + a_2k_2 + ... + a_nk_n = d$. ...
M.Shahverdi's user avatar
1 vote
1 answer
43 views

Number of steps in subtractive Euclidean algorithm

Given 2 non-negative integers a, b that range between (1 and 1e9), let c = |a - b| and after calculating c let a = b, b = c then recalculate c. what is the number of operations needed for c to reach 0....
Youssef Tarek's user avatar
0 votes
1 answer
64 views

Artin Corollary 2.3.9

I'm a bit confused on Artin's proof of Corollary 2.3.9. After defining the $\gcd$ of integers $d = \gcd(a,b)$ by $\mathbb{Z} d = \mathbb{Z} a + \mathbb{Z} b$ and $m = \text{lcm}(a,b)$ by $\mathbb{Z} m ...
Brad G.'s user avatar
  • 2,206
-1 votes
1 answer
78 views

A number when divided by 2,3,4,5,6 leaves remainder 1,2,3,4,5 respectively but when its divided by 11 the remainder is 0. FIND THE NUMBER [duplicate]

A number when divided by $2,3,4,5,6$ leaves remainder $1,2,3,4,5$ respectively but when its divided by $11$ the remainder is $0$. FIND THE NUMBER I tried taking LCM of $2,3,4,5,6$ and subratcing by $1(...
Bruh's user avatar
  • 15
0 votes
0 answers
37 views

Is $\gcd(a^n-1,a^nm) = \gcd(a^n-1,m)?$ [duplicate]

I came across this procedure while trying to solve $gcd((2^{100})-1,(2^{120})-1))$, the procedure yielded correct result. E.g $gcd((2^{120})-1,2^{100}-1))$ =$gcd((2^{100})-1,2^{120}-2^{100}))$ = $gcd((...
Optimus's user avatar
  • 11
0 votes
0 answers
39 views

Using Chinese Remainder theorem to find number of solutions of modular exponentiation mod composite number [duplicate]

I am struggling to understand a simple fact that should follow from the Chinese remainder theorem. Suppose we have a system of equations. $$ x^n = 1 (mod\ p) $$ $$ x^n = 1 (mod\ q) $$ Where $p, q$ are ...
user9855939's user avatar
0 votes
0 answers
55 views

If $\gcd(a,bc)=d$, we can say that $d|a$ and $d|bc$ but what about $d|b$, $d|c$ individually? [duplicate]

I am learning about the proof of the theorem: If $(b,c)=1$, then $(a,b)(a,c)=(a,bc)$. I have completed more than half of the theorem proof but at the end I let $(a,bc)=d$, and i know that $d \mid a,d \...
Muhammad Seyab's user avatar
0 votes
0 answers
48 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 ...
Mani's user avatar
  • 349
0 votes
0 answers
30 views

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$...
hmm1's user avatar
  • 53

1
2 3 4 5
53