Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

As is well known, if $x,y$ are natural numbers then their GCD $(x,y)$ has a representation $(x,y) = ax + by$ where $a,b$ are natural. Now let's prove that if $(x,y)=1$ then $(xy,x+y) = 1$. Starting from $ax+by=1$, $$1 = (ax+by)^2 = a^2x^2 + b^2y^2 + 2abxy = (a^2x+b^2y)(x+y) - (a-b)^2xy.$$ The reverse implication is trivial in this method. The proof can be generalized to show that if $(x,y,z)=1$ then $(xyz,xy+xz+yz,x+y+z)=1$ and vice versa.

Can this idea be molded into a reasonably strong formal proof system for some fragment of number theory?

We're competing with divisibility proofs, which we'd like to forbid somehow. For example, the original statement can be proven as follows. Suppose $p$ is a prime dividing $(xy,x+y)$. Since $p|xy$ and $p$ is prime, either $p|x$ or $p|y$. From $p|x+y$ we get that $p|(x,y)$.

share|cite|improve this question
up vote 6 down vote accepted

First, work with ideals, which provides much more power and transparency. For example, in terms of ideals your first proof is simply:

$\rm\quad\quad (x,y) \ \supset\ (xy,\ x+y)\ \supset\ (x,y)^2\ \ $ therefore $\rm\ \ (xy,\ x+y)\ =\ 1\ \iff\ (x,y)\ =\ 1$

Notice how employing ideals has eliminated obfuscatory information such as the extraneous coefficients $\ a,\:b\ $ in the original proof. That done, the innate structure becomes much clearer.

Second, there are various generalizations of the Grobner basis algorithm over Euclidean domains. Whether or not they will suffice for your application is hard to say without knowing further details.

share|cite|improve this answer
How about the Nullstellensatz? Does it say anything about the power of my potential system? – Yuval Filmus Nov 24 '10 at 4:22
@Yuval: It's still not clear to me what you are attempting to achieve. Perhaps it would help to give some further explicit examples that hint at the scope of your goals. – Bill Dubuque Nov 24 '10 at 14:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.