Existence of $1 \le r \le z^3$ such that $n \equiv 6r \mod z^3$.

40 Views Asked by At

This is a without-proof-claim inside the proof of the existence of G(3) Sec. 21.2. Hardy's Number Theory book...

Let $z=6k+1$, a 'large' integer. Let n be any integer in the interval $11z^9 + (z^3 + 1)^3 + 125z^3 \le n \le 14z^9$. Why always an integer $r$ exists such that $1 \le r \le z^3$ and $n \equiv 6r \mod z^3$?

1

There are 1 best solutions below

0
On BEST ANSWER

The assumption $11z^9+(z^3+1)^3+125z^3\le n\le 14z^9$ is, in fact, irrelevant, the important things being that

  • the integers from $[1,z^3]$ form a complete residue system modulo $z^3$;

  • $\gcd(z,6)=1$.

Consequently, as $r$ runs over the integers of the interval $[1,z^3]$, the products $6r$ also run over a complete residue system modulo $z^3$. Thus, for any integer $n$ there is some $r\in[1,z^3]$ such that $n\equiv 6r\pmod{z^3}$.