Chinese Remainder theorem: How is it used in this passage?

57 Views Asked by At

I am trying to understand this passage in 'Number theory and geometry' by Álvaro Lozano-Robledo :

enter image description here

How is the Chinese Remainder theorem used here, exactly ?

My understanding is that the $s$ and $t$ need to be relatively prime ie $\gcd(s,t)=1$ ?

Also what is the meaning of $ P \mod s$ in this context where $P=(1/3,1/3)$ ?

1

There are 1 best solutions below

0
On BEST ANSWER

The CRT is used in the standard way. Since $(3,m)=1$, there's an inverse for $3\pmod m$. Hence in $\Bbb Z/m\Bbb Z$, $1/3$ makes sense.

You probably know that if $(3,t)=1$, then $3$ has an inverse mod $t$. Say $t=2$. Then $1/3=1$, since $1\cdot3\cong1\pmod2$.

For instance, in the case of $m=15$, it is necessary that $s=3$ and $t=5$. So we can work everything out.

I recommend doing the suggested exercise in this case, to get a feel for what's going on.

So, compute $1/3\pmod5$. I get $2$. So in $\Bbb Z/5\Bbb Z$, we have $P=(2,2)$. Now do $Q$ in $\Bbb Z/3\Bbb Z$. I get $Q=(0,2)$.

Now use CRT, to get $R$. We get $R=(12,2)\in C(\Bbb Z/15\Bbb Z)$.

And we can check that $2\cdot12^2+7\cdot2^2\cong1\pmod{15}$.

This procedure works for any $m\gt1$. Thus we have an example of a diophantine equation that has solutions mod $m$ for every $m$ greater than $1$, but which has no integral solutions. However, it has rational solutions.

The author has broken the problem into $3$ cases. The key, which he didn't make very clear, is that in case $m$ is a multiple of $15$, it will be possible to write $m=s\cdot t$, with $s$ and $t$ relatively prime, as well as having $(s,5)=1=(t,3)$. This is clear. Just put $t=5^k$, where $k$ is the greatest power of $5$ that divides $m$. This should resolve your issue.