MHB Can GCD of m and n be forced to equal 1 for given equations and conditions?

[Terry1]

Hi,

I have 2 equations...

m = x + y + 1
n = x - y

where x > y > 0

I have 2 requirements of the above

m and n must be of opposite parity (which they are)
and I also require GCD(m, n) = 1, i.e. coprime.

Is there a way of selecting x and y so this condition is met?

For example, if I let x = 10 then m and n are coprime when y = {2, 5, 6, 8, 9} and not coprime when y = {1, 3, 4, 7}

Thanks for any help you can give.

 

[PaulRS]

Condition. Observe that
$$
m + n = 2\,x + 1\,,\qquad m-n=2y+1\,.
$$
Under your hypothesis, I suggest you prove that
$$
\gcd(m,n)=\gcd(m+n,m-n) = \gcd(2x+1,2y+1)\,.
$$
Here the fact that $m+n$ and $m-n$ are odd (well, that at least one of them is odd) will be crucial.

Example. When $x=10$ you have $2x+1=21 = 3\cdot 7$, and so it follows that your conditions hold iff $2y+1$ is not a multiple of $3$ or $7$.

Finding a $y$ once $x$ is fixed. Now, fixed an $x$, how do you choose $y < x$ satisfying the above requirements? Well, try proving that $\gcd(2x-1,2x+1)=1$ and so picking $y = x-1$ is actually enough because $2y+1=2x-1$ in that case.

 

[Terry1]

Hi PaulRS,

Thanks for your reply.

I did forget to mention that I am only dealing with integers, but I think that is clear from the post. Maybe I should have put it in the Number Theory sub-forum.

I'm not sure if you understood my question correctly as I'm not putting forward a hypothesis.
Anyway, I'll try to answer the points you have made...

As you have pointed out, m + n = 2x + 1 and m - n = 2y + 1, so I'm not sure I follow your

"Here the fact that m+n and m−n are odd (well, that at least one of them is odd) will be crucial."

since (m + n) and (m - n) are both patently odd."gcd(m, n) = gcd(m+n, m-n)= gcd(2x+1, 2y+1)"
Well the last two, gcd(m+n, m-n)= gcd(2x+1, 2y+1) have the same values in the brackets so the gcd is obviously the same.

gcd(m, n) = gcd(m+n, m-n)
let m = 3a and n = 3b where a and b are coprime, then gcd(m, n) = 3

m+n = 3(a+b) and m-n = 3(a-b) => gcd(m+n, m-n) = 3

Finding a y once x is fixed. Now, fixed an x, how do you choose y<x satisfying the above requirements? Well, try proving that gcd(2x−1,2x+1)=1 and so picking y=x−1 is actually enough because 2y+1=2x−1 in that case.

That is true but what I need are all valid values of y for any given x to satisfy gcd(m, n) = 1

The lines I am thinking along is if I can make a substitution for x and y such that x + y + 1 and x - y will always be coprime without having to test gcd.
Basically the same way that if you require p to be even and q to be odd you can
let p = 2s and q = 2t+1Thanks again

 

[PaulRS]

gcd(m, n) = gcd(m+n, m-n)
let m = 3a and n = 3b where a and b are coprime, then gcd(m, n) = 3

m+n = 3(a+b) and m-n = 3(a-b) => gcd(m+n, m-n) = 3

I do not know what you mean by that, in fact, you want $m$ and $n$ to be coprime, not be both multiples of $3$.

The proof is rather simple and I am going to spell it out completely so that you see the method to it, let $d$ be the greatest common multiple of $m$ and $n$. Then clearly $d$ divides $m+n$ and $m-n$ (simply factor the $d$ out from both!), thus $d\leq d^\prime$, the greastest common divisor of $m+n$ and $m-n$, since $d$ is a common divisor of these.

Similarly, $d^\prime$ divides both $(m+n)+(m-n)=2\,m$ and $(m+n)-(m-n)=2\,n$, but! since $m+n$ and $m-n$ are odd, then $d^\prime$ is odd, thus $d^\prime | (2\,m)$ means $d^\prime | m$ and similarly $d^\prime |n$. Thus $d^\prime$ is a common divisor of $m$ and $n$ and $d^\prime \leq d$, because $d$ was the greatest common divisor of $m$ and $n$.

What yo conclude from this is that $d = d^\prime$.

That is true but what I need are all valid values of y for any given x to satisfy gcd(m, n) = 1

The lines I am thinking along is if I can make a substitution for x and y such that x + y + 1 and x - y will always be coprime without having to test gcd.
Basically the same way that if you require p to be even and q to be odd you can
let p = 2s and q = 2t+1

Then you are in trouble, because, according to what I showed the condition for $y$ is $\gcd(2x+1,2y+1)=1$, and it is necessary as well as sufficient. Thus your substitution should naturally produce, not one, not two, but all of the odd integers coprime to $2x+1$ that are in the range $\{3,\ldots,2x-1\}$, and I do not think that is possible because the number (meaning 'quantity') of such integers is very irregular (at some point you will have to filter the results).

A little more technical note. If you pick an $x$ you have $$\text{number of solutions }y = \frac{\phi(2x+1)}{2} - 1\,,$$ where $\phi$ is the Euler totient function, since $n\mapsto 2x+1-n$ maps an odd number coprime to $2x+1$ into an even number coprme to $2x+1$ bijectively (and then you have to substract $1$ to take into account that $2\cdot 0 + 1$ is not a valid solution).

Conclusion. With this what I am telling you is that your "substitution for x and y" should naturally take into account the number of integers between $1$ and $2x+1$ that are coprime to $2x+1$ (that is, $\phi(2x+1)$) which I do not expect to happen for $\phi$ is such an irregular function.

I showed you a simple pair $y=x-1$ that always works. If want to have all of them, maybe you will require more assumptions on $x$ and $y$.