1

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 $$\frac{a(e-gq)}{n_1}=m \tag1$$ and so $$q=\frac{ae-mn_1}{a g} \tag2$$ for some integer $n_1$. Now $$\frac{(q^2-d)g+(e-gq)(q-p)}{n_2}=m \tag3$$ for some integer $n_2$. Substituting for $q$ from $(2)$, I have $$a (e^2-d g^2)=m(n_2 a g+n_1 (e+g p)) \tag4$$ Therefore I conclude $$\gcd\big(a (e-gq),(q^2-d)g+(e-gq)(q-p)\big)=\gcd\big(a (e-gq),a(e^2-d g^2)\big) \tag5$$

But this seems to be wrong. A simple substitution of $e1=4,g1=1,a=-3,d=17,q=5, p=4$ shows there is something not correct.

Can someone please point me where I am going astray? What then is the correct simplification?

Thanks.

John Bull
  • 33
  • Which value do you choose for $p$ in your counterexample? Did you test it line by line to detect the mistake? What are the details leading to $(4)?$ – Anne Bauval Jul 20 '23 at 12:10
  • Ah sorry.. forgot $p$.. now edited to include it. I do not understand your question regarding details leading to $(4)$.. It is a simple substitution from $(2)$. Could you please clarify? – John Bull Jul 20 '23 at 12:29
  • The claim in $(5)$ is clearly incorrect since that RHS gcd is divsiible by $,a,$ but the original gcd need not be. Generally if $(a,b)=1$ then $,(b-aq,a^2)=1,$ so $, d := (b-aq,,c_2 q^2+c_1 q+ c_0) = (b-aq, a^2(c_2 q^2+c_1 q+ c_0)) = (b-aq,, c_2b^2 + c_1 b a + c_0 a^2 ),$ since $,aq\equiv b\pmod{b-aq}\ \ $ – Bill Dubuque Jul 20 '23 at 14:00
  • @BillDubuque I do not understand what you mean at all. What are $q$ and $d$ in your explanation? Can you please correct the answer? Also the gcds are missing. – John Bull Jul 20 '23 at 16:05
  • As I wrote, $d$ is defined to be the gcd I compute, and $q$ is any integer. My notation does not connect to yours except for $,q.,$ The notation $(x,y) := \gcd(x,y),$ is standard in number theory. – Bill Dubuque Jul 20 '23 at 16:10
  • Could you please double check and clarify how your substitution from $(2)$ leads to $(4)$? I find a different litteral and numerical result. I also doubt your $(4)\implies(5)$ (see Bill's objection). – Anne Bauval Jul 20 '23 at 16:32
  • @AnneBauval Oops.. you are right indeed.. There was a sign error in (3) that I have corrected and so everything that follows is now okay. Regarding the objection, I do not understand why it is so. Maybe could you or someone else please explain it? Thank you. – John Bull Jul 20 '23 at 21:58
  • Bill already pointed the fact that $a$ divides the RHS of $(5)$ but generally not the LHS (why should it?). Your mistake was the following. Let $A=a(e-gq),B=(q^2-d)g+(e-gq)(q-p),m=\gcd(A,B),C=a(e^2-dg^2).$ You proved that $m$ divides $C,$ but this does not imply $m=\gcd(A,C).$ – Anne Bauval Jul 20 '23 at 22:09
  • @AnneBauval I see.. But then is there a simplification of that gcd? Or this is the final reduced form? – John Bull Jul 20 '23 at 22:43
  • There is no simplification. – Anne Bauval Jul 21 '23 at 04:11

0 Answers0