Goldbach’s Conjecture over Z/mZ

Goldbach’s Conjecture states that every even integer greater than 2 can be written as sum of 2 primes. This problem is notoriously difficult, and still open.

However, one can prove the following version of Goldbach’s Conjecture for the ring \mathbb{Z}/m\mathbb{Z}:

Proposition. Let m be a positive integer. Given any even integer 2n there exist primes p and q such that 2n=p+q \ (\textrm{mod } m).

The proof will, in fact, show that infinitely many such primes p and q exist. The required ingredients are Dirichlet’s Theorem on Arithmetic Progressions, and the following lemma due to Schinzel (1958):

Lemma. Given positive integers m and n, there exists an integer c such that \textrm{gcd}(c, m) = \textrm{gcd}(2n-c, m)=1.

Proof of Lemma. The case m=1 is trivial, so assume m>1 and write its prime factorization. We have m=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{r}^{\alpha_{r}} where p_{1}, ... p_{r} are distinct primes, \alpha_{1}, ... \alpha_{2} are some positive integers. For each i\in\{1, 2, ... m\}, we will show that there exists an integer c_{i} such that \textrm{gcd}(c_i, p_i) = \textrm{gcd}(2n-c_i, p_i)=1. If p_i=2, we can let c_i=1. If p_{i} is an odd prime, p_{i} cannot divide both 2n-1 and 2n+1 (otherwise, it would divide their difference which is 2); so if \textrm{gcd}(2n-1, p_i)=1 let c_i=1, and if \textrm{gcd}(2n+1, p_{i})=1 let c_i=-1. Now, by Chinese Remainder Theorem, one can find an integer c such that c\equiv c_i \ (\textrm{mod } p_{i}) for each i. It is evident that  \textrm{gcd}(c, m) = \textrm{gcd}(2n-c, m)=1. (If it is not evident, assume \textrm{gcd}(c, m)>1. Then some prime divisor of m would divide c. But it doesn’t.)

Proof of Proposition. From the lemma, we have \textrm{gcd}(c, m) = \textrm{gcd}(2n-c, m)=1 for some positive integer c. By Dirichlet’s Theorem, there exist primes p and q of the form p=m k + c and q=m \ell + (2n-c). Thus, p + q = m(k+\ell)+2n which proves 2n=p+q \ (\textrm{mod } m), as desired. Indeed, Dirichlet’s Theorem guarantees the existence of infinitely many such primes p and q.


This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Goldbach’s Conjecture over Z/mZ

  1. Robin Whitty says:

    Very appealing! You write mod p instead of mod m, though, in the statement and proof of the proposition.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s