Stack Exchange Network

Stack Exchange network consists of 175 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

New answers tagged

2

Not necessarily directly. Because: $$\gcd(k,a(b-f))\geq a\tag{1}$$And,$$\gcd(k,ag)\geq a\tag{2}$$ And, $$\gcd(a(b-f),ag)\geq a\tag{3}$$ Gets us an upper bound on a, unless k has just 1 divisor less than this (1 is a divisor trivially sadly) we can't get an exact value yet. But, putting each possible a value through a similar test might help. Especially, if ...


0

Bézout's theorem states that if $\gcd(a,b)=d$, then exists some $p,q \in \mathbb{Z}$ such that: $$ap+bq=d$$ then, you have to multiply by $\frac{n}{d}$: $$a\left( \frac{pn}{d} \right) + b\left( \frac{qn}{d} \right) = n$$ and notice that: $$a\left( \frac{pn}{d}{{\color{red} {-1}}} \right) + b\left( \frac{qn}{d}+{{\color{red} {\frac{a}{b}} }} \right) = n$...


0

I believe IV is the case where the man swims directly across the river with respect to the water. On the other hand, V is the case where he swims directly across the river in the ground frame (He swims at a slight angle to balance the drifting effect of the current).


0

Suppose $a,b,c,d$ are positive integers such that $$ \begin{cases} (ad - bc){\,|\,}a\\[4pt] (ad - bc){\,|\,}c \end{cases} \qquad $$ Fix a positive integer $n$. Let $g=\gcd(an+b,cn+d)$. Our goal is to show $g=1$. Let $h=\gcd(a,c)$. Letting $a_1=a/h$ and $c_1=c/h$, we get $$ \begin{cases} a=ha_1\\[4pt] c=hc_1\\ \end{cases} \qquad\;\;\;\;\;\;\, $$ where $...


0

By hypothesis $\ \delta := ad\!-\!bc\mid a,c,\ $ therefore $\,1 = d(a/\delta)-b(c/\delta)\,\Rightarrow\,\color{#c00}{(b,d)\,=\,1}\,$ so by $\rm\color{#0a0}{Euclid}$ $a(cn\!+\!d) -c(an\!+\!b) = \delta$ $\,\Rightarrow\, (an\!+\!b,cn\!+\!d) =\underbrace{(an\!+\!b,cn\!+\!d,\,\color{#0a0}\delta) = (\color{#c00}{b,d},\delta)}_{\!\!\!\large \begin{align}&an+b\ ...


0

Let $g = \gcd(a,c)$. Since $g \mid a$ and $g \mid c$, we get $g \mid ad-bc$. Since $ad-bc \mid a$ and $ad-bc \mid c$, then $ad-bc$ is a common divisor of $a$ and $c$, so $ad-bc \mid g$. Now, $g \mid ad-bc$, and $ad-bc \mid g$. So $g = \pm (ad-bc)$. For simplicity let's assume $g = ad-bc$. (If $g = -(ad-bc)$, then either go through a similar argument to the ...


0

Suppose that $a = x(ad-bc)$ and $c = y(ad-bc)$. Then $$ad-bc = [x(ad-bc)] \cdot d - b[y(ad-bc)] = (dx - by) (ad - bc).$$ However, since $(ad-bc) \mid a$, and $a$ is positive, it follows that $ad - bc \ne 0$. Thus, we must have that $dx - by = 1$, from which we can conclude that $\gcd(b,d) = 1$ (which proves the case of $n = 0$). Now, for the general case, ...


0

Hint: For any ring $R$ and any ideals $I, J\subset R$, one has $$I\cdot R/J=(I+J)/J,$$ so $\;\langle h,k\rangle\cdot \mathbf Z/n\mathbf Z=\langle h,k,n\rangle/n\mathbf Z $.


2

Let us consider the numbers that can be formed by $\alpha-1$ additions: \begin{align} \alpha =1 \text{ gives }& \mathcal{A}_1 =\{a,a+1,\ldots, a+(b-a)\}\\ \alpha =2 \text{ gives } & \mathcal{A}_2 =\{2a,2a+1,\ldots, 2a+2(b-a)\}\\ \alpha =3 \text{ gives } & \mathcal{A}_3 =\{3a,3a+1,\ldots, 3a+3(b-a)\}\\ &\vdots\\ \text{In general, } \alpha \...


1

If you start with $a\neq b$ (i.e. if your starting set contains more than one number) then the set of numbers that "can be formed" will always be cofinal in the natural numbers (i.e. there will always be a $n$ s.t. every $m>n$ could be obtained via additions). To see this, assume you start from $\{n,n+1\}$. Notice that if you consider the possible ...


3

Cancelling $\,d = (a,b)\,$ from both sides reduces it to the case where $\,(a,b) = 1.\,\,$ Then it becomes $\, 2 = (a-b,\,a+b)\,$ for $a,b\,$ odd and coprime. Proof: $ $ clearly $\,2\mid a-b,a+b\,$ by $\,a,b\,$ odd. Conversely $\,c\mid a-b,a+b\,\Rightarrow\, c\mid 2a,2b\,\Rightarrow\, c\mid (2a,2b)=2(a,b)=2.\ $ QED Alternatively: $\,a\!+\!b,\,a\!-\!b\,$ ...


2

$ D=(a,b)$ so that $D|a,\ D|b,\ 2D=(2a,2b)$ and $D$ is odd Hence $D|a+b,\ D|a-b$ so that $D|(a+b,a-b)$ Since $a+b,\ a-b$ are even, $2D|(a+b,a-b)$ When $D'=2kD|(a+b,a-b),\ k>1$, then $$2kD=D'|(a+b)-(a-b)=2b ,\ kD|b$$ Similarly, $kD|a$ so that it is a contradiction to $D=(a,b)$


2

Let $D=\gcd(2a,2b)$ and $d=\gcd(a+b,a-b)$ Clearly $2\,|\,D$ so let $D=2E$. As you note, $E=\gcd(a,b)$. It is clear that $2\,|\,d$, and it is clear that $E$ is odd. To see that $E\,|\,d$ we remark that $E$ must divide both $a$ and $b$, hence $E$ divides $a\pm b$ and we are done.


0

This may not be what you want, but the completion can be done as follows. Let $x=x_1$ be the given integer vector. We look for $2n-1$ integer vectors $x_2,\ldots,x_n,y_1,\ldots,y_n$ such that $$ Y^TX=\pmatrix{y_1^T\\ y_2^T\\ \vdots\\ y_n^T}\pmatrix{x_1&x_2&\cdots&x_n} =\pmatrix{1&\ast&\cdots&\ast\\ &1&\ddots&\vdots\\ &...


0

Hint: Suppose $f(n)<n$. Then $\gcd(f(n),n)\leq n/2$ and $\operatorname{lcm}(f(n),n)\geq n$, so $\operatorname{lcm}(f(n),n)-\gcd(f(n),n)\geq n/2$. Similarly for $f(n)>n$. So you only need to check the possible $f(n)$ for a few values of $n$.


0

Applying this answer: wlog $\,m < n\,$ so $\,d = (2^m,2^n) = 2^m,\ b = 1,\ c = 2^{n-m}.\ $ Thus $\,2\nmid b-c\,$ so the formula there implies that the gcd $ = (a^d+1,2) = 1$ if $a$ is even, and $2$ if $a$ is odd. Alternatively a more direct proof follows as below (from this answer on Fermat numbers). ${\bf Hint}\rm\quad\ \ \gcd(c+1,\,\ c^{\large 2k}\!+...


2

Good work so far. The "problem" with the first solution, $(\alpha, \beta) = (-2, 1)$, is that the $-2$ is negative. And so you add $(4, -2)$ to it to get a new solution $(4, -1)$, and now the first entry is positive and you're good to go. Let me answer in two ways from here: how do you find $(p, q) = (4, 2)$, the "thing to add"? Well, you know that $\...


0

The question is not always true; if $p \mid a+b$ the $\gcd$ may not be $1$, e.g. when $(a,b,p) = (1,2,3)$ we get $\frac{a^p+b^p}{a+b} = 3 = a+b$. So we further assume that $\gcd(a+b, p) = 1$, and show that $\displaystyle \gcd \left( a+b, \frac{a^p+b^p}{a+b} \right) = 1$. Suppose that some prime $q$ divides both $a+b$ and $\frac{a^p+b^p}{a+b} = a^{p-1} - a^{p-...


1

Your updated original statement & proof looks correct. Regarding your main question about the distribution of the values of $x$ where $\gcd(x(x+2),p\#) = 1$ for various primes $p$, I'll first provide an argument why there's actually very likely no upper bound on the maximum number in any single sub-range, and then give you an example where there are $3$ ...


0

Since the OP had the word intuition in the title, this answer 'paints a picture' that can be examined for another viewpoint/angle. The wikipedia states The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. Division is ...


2

The first key is: Theorem 1: If $a_1,\cdots,a_k$ are positive integers which are pair-wise relatively prime (that is, $\gcd(a_i,a_j)=1$ when $i\neq j$) we have that $$\operatorname{lcm}(a_1,\dots,a_k)=\prod_{i=1}^{k}a_i$$ The second key is: Theorem 2: if $a_1,\cdots,a_k$ are positive integers then there are pair-wise relatively prime integers $a_1',\...


1

If you are still interested in a solution using GCD: In order to fit exactly for both walls it is necessary for the side length of a tile to divide the GCD of $120$ and $216$: $$(120,216) = 24 \Rightarrow 12 \mbox{ is the fitting tile side}$$


2

You do not need GCD or LCM at all here. The tile that will fit is the one whose length evenly divides both the room's dimensions. $10$ cm doesn't divide into $216$ cm (the room length, converted from metres), and neither does $18$ cm divide into $120$ cm (the width), so the tile of $12$ cm fits, with sides of $10$ and $18$ tiles.


4

Since the $\gcd$ has to be a divisor of $7x-y$ and $x+2y$, it has to divide twice the first plus the second, or $15x$. It also has to divide the $7$ times the second minus the first, or $15y$. Therefore, it has to divide $\gcd(15x,15y)=15$. Thus the four possible values are $1,3,5,15$ obtained on the pairs e.g $(2,1),(1,1),(1,2),(4,13)$.


-1

You may or may not be able to generate primitive triples with your function because it reads the same as Euclid's formula except with $A$ and $B$ reversed and all the terms divide by $2$. For Euclids $(m,n)=(2,1)$ you would get $(2,1.5,2.5)$ as a triple. Let's try your equation with terms multiplied by $2$ and with $A,B$ reversed. $\text{We are given }\quad ...


1

I assume you mean $m, n \in \mathbb{N}$, and you're referring to the polynomial $\gcd$. We claim the following answer: if $m$ and $n$ have the same highest power of $2$, then $\gcd(x^m+a^m, x^n+a^n) = x^d+a^d$ where $d = \gcd(m,n)$, and a constant polynomial otherwise. To prove this, we first replace $x$ with $ax$ to reduce the problem to $\gcd(x^m+1, x^n+...


-1

If ( 2 and n ) have greatest common divisor only 1 ,then obviously ( 2*2*2.... ) and n will have greatest common divisor 1 So , gcd ( 2 ^ k , n) =1


1

$$ \left( x^{4} + x^{2} + 1 \right) $$ $$ \left( x^{4} - x^{2} - 2 x - 1 \right) $$ $$ \left( x^{4} + x^{2} + 1 \right) = \left( x^{4} - x^{2} - 2 x - 1 \right) \cdot \color{magenta}{ \left( 1 \right) } + \left( 2 x^{2} + 2 x + 2 \right) $$ $$ \left( x^{4} - x^{2} - 2 x - 1 \right) = \left( 2 x^{2} + 2 x ...


1

I think most efficiently it's the following. $$x^4-x^2-2x-1=x^4-(x+1)^2=(x^2-x-1)(x^2+x+1).$$ $$x^4+x^2+1=(x^2+1)^2-x^2=(x^2-x+1)(x^2+x+1).$$ Can you end it now?


3

You got the GCD in $\mathbb Z[X]$, i.e. $X+1$. The GCD in $\mathbb Z / 5 \mathbb Z[X]$ is obtained by reducing each coefficient of the GCD in $\mathbb Z$ in $\mathbb Z / 5 \mathbb Z$. Which means that the GCD in $\mathbb Z / 5 \mathbb Z[X]$ is equal to $\bar{1}X + \bar{1} = X + \bar{1}$.


2

HINT It's easy to see that $x^2-x-2 = (x+1)(x-2)$, but in $\mathbb{Z}/5\mathbb{Z}$ you have $5 \equiv 0$, so $$ x^3+9x^2+10x+3 \equiv x^3-x^2+3 = (x+1)\times \ldots $$


2

You also have the solution of $$x= 45\times 125$$ Note that in this case $L=45\times 125$ and $G=125$ thus $L=45G$ In general If $G(x,y)=d$, then $x=md$ and $y=nd$ where $G(m,n)=1.$ Using this fact may help reduce calculations in more complicated cases.


2

In addition to your argument that $9 \mid x$, you know that $125 \mid L$, requiring $125 \mid 45 G$, so $25 \mid 9 G$, forcing $25 \mid G$. But this means $25 \mid 125$ and $25 \mid x$. Then we know $9 \mid x$ and $25 \mid x$, so $225 \mid x$.


Top 50 recent answers are included