# congruence

• Sep 10th 2010, 03:11 AM
Shanks
congruence
Show that for any positive integer $n$, there exist a prime number $p$ and another positive integer $m$ such that:
(1) $p$ is a prime numer of form $6k+5$;
(2) $n$ is not a multiple of $p$;
(3) $n-m^3$ is a multiple of $p$.
• Sep 10th 2010, 06:18 AM
undefined
Edit: nevermind, didn't think it through.

Edit 2: Here are some thoughts.

p being congruent to 5 mod 6 is the same as saying p is an odd prime congruent to 2 mod 3.

Here is an experiment: Note that

$1^3\equiv1\pmod{11}$

$2^3\equiv8\pmod{11}$

$\dots$

$10^3\equiv10\pmod{11}$

produces all equivalence classes mod 11 besides zero.

If this is true for all odd primes congruent to 2 mod 3 and we can prove it, then the only other piece we'd need is that there exist an infinitude of such primes.
• Sep 10th 2010, 08:00 AM
roninpro
We can rephrase this in the language of congruences:

(1) $p\equiv 5\pmod{6}$
(2) $n\not \equiv 0\pmod{p}$
(3) $n\equiv m^3\pmod{p}$ has a solution

With this in mind, it suffices to show that the map $f:\mathbb{Z}_p\to \mathbb{Z}_p$ defined by $f(x)=x^3$ is a bijection. Can you do this?