I have the following problem: I have to show the following just by using number theory:

$\forall x_o,x_1\in \mathbb{Z}\quad \exists k_0,k_1\in \mathbb{N} \quad \exists y_0,y_1\in \mathbb{Z}: x_0^{k_0}(x_1^{k_1}(1+x_1y_1)+x_0y_0)=0$.

I'm not allowed to use the criteria of coquand and lombardi.

I thought about the following: if $x_0=0$ or $x_1=0$ then you just set $y_0=0$ and the above is shown. So we now set $x_0,x_1\neq 0$. Because $\mathbb{Z}$ is an integrity ring $x_0^{k_0}=0$ or $(x_1^{k_1}(1+x_1y_1)+x_0y_0)=0$. Since $x_0\neq 0$ the other term $(x_1^{k_1}(1+x_1y_1)+x_0y_0)$ has to equal $0$. There are $2$ possible cases:

$1) \ (1+x_1y_1)=0$ and $x_0y_0=0$. This is only possible if $x_1\in\{1,-1\}$. $2)\ x_1^{k_1}(1+x_1y_1)=-x_0y_0$. So my question here is:

Is the following true?:$\ \forall x_0,x_1 \quad \exists k_1,y_1$ so that $x_0\ |\ x_1^{k_1}(1+x_1y_1)$

Can somebody help me please? Thanks in advance.

  • $\begingroup$ Does $*$ stand for multiplication? $\endgroup$ – Arnaud Mortier May 23 '18 at 21:51
  • $\begingroup$ That's right. I forgot to use cdot $\endgroup$ – Tobi92sr May 23 '18 at 21:58
  • $\begingroup$ In this case you can just use nothing. It's much easier to read. $\endgroup$ – Arnaud Mortier May 23 '18 at 22:00

Good job for simplifying the problem.

Write $x_0=ab$ where $b$ is the largest factor of $x_0$ that is coprime with $x_1$. In other words, $a$ is the factor of $x_0$ made of all prime numbers that appear in both $x_0$ and $x_1$.

Picking a $k_1$ large enough will make $x_1^{k_1}$ a multiple of $a$. Large enough is, for example, larger than all powers that appear in the prime decomposition of $a$.

Now since $b$ and $x_1$ are coprime, there is a Bezout relation $$px_1+qb=1$$ which you can rewrite as $qb=1-px_1$. Let $y_1=-p$, you now have $$x_0=ab\ |\underbrace{ \ \ x_1^{k_1}\ \ }_{\text{multiple of $a$}}\cdot \underbrace{(1+x_1y_1)}_{\text{multiple of $b$}}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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