I'm trying to understand Hilbert's tenth problem and some of the proofs which show it is unsolvable. To date I've been using this paper and Hilbert’s Tenth Problem An Introduction to Logic, Number Theory, and Computability by M. Ram Murty and Brandon Fodden as a guide.
The specific issue I'm having is with the examples shown for (, ) at the bottom of page 7 of 1.
In both texts they use a function involving modulo. In both texts it is important that this function equals a natural number. However in cases where x (mod y) = 0 this would seem to lead to a contradiction. In these cases the texts simply state x (mod y) = y. Can someone explain to me why x (mod y) = y and not 0? An example of this is the case of 6 mod 2 in the
By definition of the function $S(i,u)$ its value is in the range $[1,1+iR(u)]$. That is, $$1\leq S(i,u)\leq 1+iR(u),$$ holds by definition. Note that for any integer $y$ we have $$y\equiv0\pmod{y},$$ so if $x\equiv 0\pmod{y}$ then also $x\equiv y\pmod{y}$. For the function $S(i,u)$ we simply choose a representative in the range $[1,1+iR(u)]$ for the remainder mod $1+iR(u)$.
For the example you link, computing $S(i,16)$ we see that $L(16)=6$ and $R(16)=1$, so $S(i,16)$ is the unique natural number $w$ satisfying: $$w\equiv6\pmod{1+i}\qquad\text{ and }\qquad1\leq w\leq1+i.$$ For $i=1$ this becomes $w\equiv6\pmod{2}$ and $1\leq w\leq2$. Clearly $6\equiv2\pmod{2}$ so $S(1,16)=2$.
For $i=2$ this becomes $w\equiv6\pmod{3}$ and $1\leq w\leq3$. Clearly $6\equiv3\pmod{3}$, so $S(2,16)=3$.
For $i=3$ this becomes $w\equiv6\pmod{4}$ and $1\leq w\leq4$. Clearly $6\equiv2\pmod{4}$ so $S(3,16)=2$.
Etcetera.