# congruence

• Sep 10th 2010, 02:11 AM
Shanks
congruence
Show that for any positive integer $\displaystyle n$, there exist a prime number $\displaystyle p$ and another positive integer $\displaystyle m$ such that:
(1) $\displaystyle p$ is a prime numer of form $\displaystyle 6k+5$;
(2) $\displaystyle n$ is not a multiple of $\displaystyle p$;
(3) $\displaystyle n-m^3$ is a multiple of $\displaystyle p$.
• Sep 10th 2010, 05: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

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

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

$\displaystyle \dots$

$\displaystyle 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, 07:00 AM
roninpro
We can rephrase this in the language of congruences:

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

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