Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [greatest-common-divisor]

The greatest common divisor of two or more integers is the largest integer that divides all of them (if it exists).

0
votes
1answer
19 views

Prove that gcd(a,b)=dgcd(a/d,b/d). [duplicate]

I think the strategy for this problem would be i assume some arbitrary element is in gcd(a,b) and chase it into the rhs and then do it the other way around , but i am not sure how to even start this ...
0
votes
1answer
34 views

An isomorphism between $\mathbb Z_n \times \mathbb Z_m$ and $ \mathbb Z_{mn}$

I am reading these lecture notes and they suggest the following generalisation of a specific example for $\mathbb Z_2 \times \mathbb Z_3 \cong Z_6 $: There exists an isomorphism between $\mathbb ...
0
votes
1answer
18 views

Greatest common divisor with $a \cdot s + b \cdot t = ggT(a,b)$

On the internet, I've seen the greatest common divisor with the notation $a \cdot s + b \cdot t = ggT(a,b)$ So for $a = 121$ and $b = 33$, the table is \begin{array}{|c|c|c|c|} \hline r& q & ...
3
votes
3answers
111 views

Numerical example for $\gcd(a,b)=\prod p_i^{\min(a_i,b_i)}$

I'm actually having trouble understanding the above corollary. Can anyone please provide a numerical example of that corollary? Thank You So Very Much in advance. Corollary If $a=\prod p_i^{a_i}$ ...
2
votes
3answers
61 views

Show that if $\gcd(abc,d^2)=1$, then $\gcd(a,d)=\gcd(b,d)=\gcd(c,d)=1$.

Let $a,b,c$ be integers. Show that if $\gcd(abc,d^2)=1$, then $\gcd(a,d)=\gcd(b,d)=\gcd(c,d)=1$. Here is my way of approaching this question: Suppose $\gcd(abc,d^2)=1$, there exist integers $x,y$ ...
4
votes
2answers
45 views

Find x such that $495x \equiv 90 \pmod{6}$ or explain why it does not exist

The questions are: i) Find $\gcd(315, 495)$ ii) Find $x$ such that $495x \equiv 90 \pmod{6}$ or explain why it does not exist I did (i) and got $\gcd(315, 495)=45$. How do I find the answer for (ii)...
1
vote
0answers
31 views

Show that there exist $a,b \in K [X_1,X_2,\cdots,X_n]$ and $d \in K[X_1,X_2,\cdots,X_{n-1}]$ such that $aF+bG = d.$

Let $K$ be a field. Let $F,G \in K [X_1,X_2,\cdots,X_n]$ be two polynomials which are relatively prime to each other. Show that there exist polynomials $a,b \in K [X_1,X_2,\cdots,X_n]$ and $0 \neq d \...
2
votes
1answer
46 views

trying to prove that if m, n and a are in the integers then $gcd(m, n) = gcd(n, m - an)$

So in trying to formulate this proof, based on the statement that: $gcd(m, n): ∀m, n, a ∈ \mathbb Z,∃ e \in \mathbb N, ((e|m ∧ e|n) ∧ (∀ d ∈ \mathbb N, d|n ∧ d|m \Rightarrow d\leq e))$ I've ...
0
votes
4answers
98 views

Prove gcd(f(n), f(n+1))=1

Let $f: N \implies N$ be the function $f(n)=n^2+n+1$. Prove for all $n \in \mathbb{N}, gcd(f(n), f(n+1))=1$. I was able to prove that both $f(n)$ and $f(n+1)$ are odd for all $n$ but now I am stuck. ...
0
votes
3answers
175 views

Prove $\gcd(m, n)=\gcd(m, 2n)$

For all integers $m$ and $n$, if $m$ is odd, prove $\gcd(m, n) = \gcd(m, 2n)$. There is an external fact that can be used if both numbers are odd, their product is odd as well. I think I need to prove ...
2
votes
4answers
69 views

What are $x$ and $y$ in $xF_n$ + $yF_{n-1}$ = $1$?

We know that the $\gcd$ of consecutive Fibonacci numbers is $1$. But while finding the coefficients $x$ and $y$ in using euclidean algorithm in reverse direction I am not able to find any pattern so ...
3
votes
1answer
49 views

If $\sigma(n)/n = 5/3$, then $5 \nmid n$. Does it also follow that $3 \nmid \sigma(n)$?

Let $\sigma(x)$ denote the sum of divisors of the positive integer $x$. Denote the abundancy index of $x$ by $I(x)=\sigma(x)/x$. If $\sigma(N)=2N$ (equivalently, when $I(N)=2$) then $N$ is called a ...
-1
votes
1answer
49 views

Explicit expression for solutions $(x,y)$ of Diophantine equation $ax+by=d$.

Given $a,b\in\mathbb{Z}$. It is known that $\gcd (a,b)=d$ implies $$\exists x,y\in\mathbb{Z}, \ ax + by=d .$$ I have been looking for an explicit expression of any solution $(x,y)$, in terms of $a,b,...
3
votes
1answer
48 views

Find divisors $n_i$ of $a_i$, mutualy coprime, with $\prod n_i=\operatorname{lcm}(a_i)$

We are given $k$ positive integers $a_i$, and want as many positive integers $n_i$ each dividing the respective $a_i$, with the $n_i$ mutually coprime, and the product of the $n_i$ equal to to the ...
1
vote
0answers
27 views

If $gcd(a,b)=1$ then $gcd\big(\frac{a^{p}+b^{p}}{a+b},a+b\big)=1$ unless $p|a+b$ [duplicate]

If $\gcd(a,b)=1$ then $$\gcd\left(\frac{a^{p}+b^{p}}{a+b},a+b\right)=1$$ unless $p|(a+b)$ Where $p$ is any prime. Use of modular arithmetic is restricted. Can you prove it just using basic divisiblity ...
-1
votes
1answer
45 views

Prove (15n+17,10n+11) = 1 [duplicate]

I am new to number theory and wanted to know If I am doing this correctly: W.t.s. $(15n+17,10n+11) = 1$ Using the Division Algorithm we have $15n + 17 = (10n + 11)(1) + (5n + 6)$ $10n + 11 = (5n +...
0
votes
1answer
22 views

Given $k$, for every $n>1$, constructing a set of size $n$ of non-zero integers having gcd $k$ so that no proper subset has gcd $k$

For a finite subset $S \subseteq \mathbb Z \setminus \{0\}$, let us say $d=\gcd S$ iff $d>0 $ , $ d|a,\forall a \in S$ and $m|a,\forall a\in S \implies m|d$. My question is: Does there exist a ...
3
votes
2answers
157 views

Why doesn't one see more *induction on the number of primes* arguments?

I've used this proof technique to examine what happens when $ax = by$ for example. The proof worked out nicely by introducing the $n$th prime $p$. Here's exactly where I used it before What I want ...
-1
votes
1answer
21 views

Trying to compute the greatest value of $x$.

$a,b,c,x,k$ are positive natural numbers. $$86 = ax+k$$ $$142 = bx + k$$ $$252 = cx+k$$ I'm trying to compute the greatest value of $x$. Let's assume $ k = 1$ (we want x to take its greatest ...
1
vote
1answer
32 views

Let $p$ be prime, $k ∈ \mathbb{N}$ and suppose that $\gcd(k,p-1)=d$. Show that $x^k ≡ 1\pmod{p}$ has $d$ distinct solutions modulo $p$.

I'm lost here. Any help would be great. Let $p$ be prime, $k ∈ \mathbb{N}$ and suppose that $\gcd(k,p-1)=d$. Show that $x^k ≡ 1\pmod{p}$ has $d$ distinct solutions modulo $p$.
4
votes
2answers
156 views

Counting integers less than $n$ that are relatively prime to $x\#$

Let $x,n$ be integers such that $x < n$. Let $x\#$ be the primorial of $x$ so that $6\# = 5\# = 30$ and $7\# = 210$ Let gcd$(a,b)$ be the greatest common divisor of $a$ and $b$. Let $S(x,n)$ be ...
0
votes
0answers
24 views

Greatest common divisor in predicate logic with one binary functional symbol

Lets have one binary functional symbol $f$, where $f(x,y)=xy$. Show that in the universe of $\mathbb{Z}$ every two numbers have Greatest common divisor. So far my solution look like this: $$\exists ...
1
vote
1answer
37 views

Prove $\gcd(a,m) \mid \gcd(ab,m)$ $\forall a,b,m \in \Bbb Z$

I named $\gcd(a,m) = d$ and $\gcd(ab,m) = d' $ So I know that $d\mid a$, $d\mid m $ and $d'\mid ab $ , $d' \mid m$ But I can't use the transitive property of divisibility here. How can I prove ...
5
votes
2answers
40 views

If $p,q$ are distinct primes and $a$ is not divisible by $p$ or $q$, then $\gcd(a, pq)=1$ [duplicate]

If $p,q$ are distinct primes and $a$ is not divisible by $p$ or $q$, then $\gcd(a, pq)=1$. I want to show this using linear combinations, so that a linear combination of $a$, and $py$ will give $1$. ...
0
votes
1answer
19 views

Fastest way to find LCM and HCF of multiple numbers?

Is there any shortcut approach to find LCM and HCF of multiple numbers apart from prime factorization and hit and trial method (writing down all the multiples of respective numbers and comparing them ...
2
votes
1answer
34 views

Under which conditions is $\gcd(a+bx,c)=1$ solvable and what is the solution?

Let $a,b,c\in\mathbb{Z}$, $c\neq0$. When is $\gcd(a+bx,c)=1$ solvable and what is $\{x\in\mathbb{Z}\mid\gcd(a+bx,c)=1\}$? A sufficient condition appears to be $\gcd(a,b)=1$ but it is not necessary as $...
0
votes
2answers
17 views

Speed up divisors' calculation by hand

An exercise such the following one has to be solved by hand during an exam. So, knowing that I need to solve it in about ten minutes, I would like to know if there is a rapid technique to do it. ...
0
votes
1answer
29 views

Two polynomials having a quadratic common divisor

Find the real numbers a,b such that the polynomials $$p(x)=x^4-2x^3+3x^2+2x+a $$ $$q(x)=x^4-3x^3+4x^2+3x+b $$ have a common divisor of degree two. My attempt: Euclid algorithm: we perform the ...
3
votes
2answers
30 views

If $n,m \in \mathbb{N}$ then there are $c,d$ such that $cd = (m,n)$, $(c,d) = 1$ and $(m/c,n/d) = 1$.

Suppose that $m,n \in \mathbb{N}$. Using the fundamental theorem of arithmetic it is easy to show that there exist $c,d \in \mathbb{N}$ such that $(c,d) = 1$, $cd = (m,n)$ and $(\frac{m}{c},\frac{n}{d}...
0
votes
0answers
19 views

Greatest common divisor of two polynomials

If polynomials f(x) and g(x) have complex coefficients, their gcd is defined as another polynomial d(x) with the properties: 1) d(x) divides both f(x) and g(x) 2) every other polynomial d'(x) that ...
3
votes
2answers
65 views

Prove that if $ab$ is a perfect square and $GCD(a,b)=1$, then $a$ and $b$ are perfect squares

How can I easily prove that if $ab$ is a perfect square and $GCD(a,b)=1$ then $a$ and $b$ are perfect squares. I actually managed to prove that this way: if an integer $n$ is a perfect square, then ...
0
votes
3answers
37 views

How many positive integers $x \le 3600$ are there such that $\gcd(3600, x)=9$?

I'm trying to answer this question which has a hint: think about $\mathbb Z_{3600}$. I tried to set up a linear equation,$\mod{3600},$ without any success. Not even the factorization of $3600$ gives ...
0
votes
4answers
49 views

Check divisibility by using $\gcd$.

Let $k$ be an odd integer. As a part of an introductory class to proofs, I wanted to show that the number $k^2 - 1$ is divisible by $8$, and managed to do this by checking that it is congruent modulo $...
1
vote
2answers
57 views

$gcd(m,n) = gcd(a\cdot m+b\cdot n,c\cdot m+d\cdot n)$ [duplicate]

I'm trying to proof the following statement: Let $a,b,c,d \in\mathbb{Z}$ and $m,n \in \mathbb{N}$. If $ad-bc = 1$, then $gcd(m,n) = gcd(a\cdot m+b\cdot n,c\cdot m+d\cdot n)$. So first of all I ...
2
votes
1answer
45 views

Proof that there are infinitely many $k$'s such that $a + k$ and $b + k$ are coprime

I need to show that for any $a, b \in \mathbb{Z}^+$ with $a \neq b$ there are infinitely many $k \in \mathbb{Z}$ such that $a + k$ and $b + k$ are relatively prime to each other. I came up with a ...
0
votes
0answers
15 views

Signs in subresultant pseudo-remainder sequence

Subresultant pseudo-remainder sequence is way of computing remainder sequence of two polynomials in $\mathbb{Z}$ and keeping the size of coefficients relatively small, but the signs of the remainders ...
1
vote
1answer
30 views

Question pertaining to the relationship between the GCD and LCM of 3 numbers.

I am a high school student self-studying Number Theory and came across this question in the book Challenge and Thrill of Pre-College Mathematics (For reference, $(m,n)$ means $\gcd(m,n)$ and $[m,n]$ ...
0
votes
2answers
21 views

If $\sigma(n) = 2n - d$ and $d \mid n$, is it true that $d = \gcd(n,\sigma(n))$?

In what follows, assume that $d > 0$. Let $$\sigma(x)=\sum_{e \mid x}{e}$$ denote the classical sum-of-divisors function, and denote the deficiency of $x \in \mathbb{N}$ by $$D(x)=2x-\sigma(x).$$ ...
4
votes
2answers
107 views

What is the maximum value of $(a+ b+c)$ if $(a^n + b^n + c^n)$ is divisible by $(a+ b+c)$ where the remainder is 0?

The ‘energy’ of an ordered triple $(a, b, c)$ formed by three positive integers $a$, $b$ and $c$ is said to be n if the following $c$ $\ge b\geq a$, gcd$(a, b, c) = 1$, and $(a^n + b^n + c^n)$ is ...
1
vote
1answer
28 views

Integral Domain, PID and gcd

Let $R$ be a PID and $R'$ a Integral Domain and $R\subseteq R'$. Let $a,b,d \in R $ and $d$ is a gcd of $a$ and $b$ in $R$. Then $d$ is also a gcd of of $a$ and $b$ in $R'$. Proof: $d$ is a gcd of $...
0
votes
1answer
72 views

Proof Verification- Prove that $(a+b,a-b) \geq (a,b)$ for any two integers.

I came across this question while solving the book Challenge and Thrill of Pre-College mathematics. Please check if the proof that I have done is correct. (I am familiar with only basic number theory ...
1
vote
1answer
46 views

If $q \equiv k \equiv 1 \pmod 4$, is it necessarily true that $\gcd\bigg(\sigma(q^k),\sigma(q^{(k-1)/2})\bigg)=1$?

Let $\sigma$ denote the classical sum-of-divisors function. In what follows, we let $q$ be a prime number. Here is my question: If $q \equiv k \equiv 1 \pmod 4$, is it necessarily true that $\gcd\...
2
votes
4answers
49 views

Prove that $\text{gcd}(a, p) = 1 \implies p\nmid a $ is true.

This is one direction of the biconditional in part b of this proposition: Prove that for every prime, $p$, and for all natural numbers $a$, (a) $\text{gcd}(a,p)=p$ iff $p\mid a$ (b) $\text{gcd}(a,p)=...
2
votes
3answers
46 views

greatest common divisor of two elements

Find all possible values of GCD(4n + 4, 6n + 3) for naturals n and prove that there are no others 3·(4n + 4) - 2·(6n + 3) = 6, whence the desired GCD is a divisor 6. But 6n + 3 is odd, so only 1 ...
2
votes
1answer
73 views

Find the smallest positive integer $x$ satisfying $\gcd(x^n+a,(x+1)^n+a)>1$

Given positive integers $n$ and $a$, I'd like to ask how to find the smallest positive integer $x$ satisfying $\gcd(x^n+a,(x+1)^n+a)>1$? I try using the extended Euclidean algorithm on the two ...
2
votes
1answer
56 views

Can I make general formula for this problem

I want to find how many pairs of numbers satisfy this condition on $[1,n]$. For given $n$ , how many pairs $(a,b)$ are there such that $gcd(a,b) = 2^t , t > 0 $ for some whole number $t$. All ...
1
vote
0answers
48 views

Linear combination using extended GCD

Trying out different implementations of the extended GCD, i found out that all of them return the same linear combination factors for $egcd(a,b)$ and $egcd(b,a)$. For example (with this algorithm) I ...
4
votes
1answer
84 views

Why do we notate the greatest common divisor of $a$ and $b$ as $(a,b)$?

In my textbook on elementary number theory from a class last year, as well as elsewhere through my academic experience and even posts here, I often see the greatest common divisor notated as $(a,b)$ (...
4
votes
1answer
35 views

Infinite set of positive integers - choose infinitely many to be relative primes or not

Given a set of infinitely many positive integers. Is it always possible to find a subset of this set which contains infinitely many numbers such that any two numbers in this subset are relative primes ...
0
votes
4answers
49 views

LCM and GCD polynomial relationship

I need some help with constructing a proof for the following statement,$ \frac{P_1 P_2}{hcf(m,n)} = lcm(P_1,P_2)$ where $P_1$ and $P_2$ are polynomials with real coefficients. I know how to do the ...