A Diophantine Obvious Problem

Gödel’s Lost Letter and P=NP 2019-10-12

With a short solution that was hard for me to find.

[ Royal Society ]

Sir Timothy Gowers is a Fields medalist and fellow blogger. Sometimes he (too) writes about simple topics.

Today I would like to talk about a simple problem that came up recently.

The problem is a simple to state “obvious fact”. The reason I thought you might be interested is that I had a tough time finding the solution. I hope you find the explanation below interesting.

The general issue of proving obviously true statements is discussed here for example. Here is an example from Gowers:

Let ${I_{1},I_{2},\dots }$ be intervals of real numbers with lengths that sum to less than ${1}$ , then their union cannot be all of ${[0,1]}$ .

He says:

It is quite common for people to think this statement is more obvious than it actually is. (The “proof” is this: just translate the intervals so that the end point of ${I_{1}}$ is the beginning point of ${I_{2}}$ , and so on, and that will clearly maximize the length of interval you can cover. The problem is that this argument works just as well in the rationals, where the conclusion is false.)

The Problem’s Statement

The following simple problem came up the other day. Suppose that ${t}$ is an odd number. Show there is some ${x}$ so that

$\displaystyle (x,t) = 1 \text{ and } (4x+1,t) = 1.$

Here ${(a, b)}$ is the gcd, the greatest common divisor of ${a}$ and ${b}$ . For example,

$\displaystyle (21, 14) = 7.$

This result seems totally obvious, must be true, but I had trouble finding a proof.

The Problem’s Cousin

There is a unproved conjecture in number theory that says: There are an infinite number of ${x}$ so that both ${x}$ and ${4x+1}$ are prime. This clearly shows that there is an ${x}$ for our problem.

I like conjectures like this since they give you an immediate insight that a statement is likely to be true. But we would like a proof that does not use any unproved conjectures. Our problem can be viewed as a poor version of some of these conjectures. Suppose that you have a conjecture that there are an infinite number of ${x}$ so that

$\displaystyle f_{1}(x),f_{2}(x),\dots,f_{m}(x),$

are all prime for some given functions ${f_{k}(x)}$ . Then the poor version is to prove that there are ${x}$ so that these numbers are all relatively prime to some given ${t}$ . There are some partial results to the prime version by Ben Green and Terence Tao.

The Problem’s Failed Proofs

My initial idea was to try to set ${x}$ to something like ${ty + 1}$ . The point is that this always satisfies the first constraint: that is ${(ty+1, t)=1}$ for any ${y}$ . Then I planned to try and show there must be some ${y}$ that satisfies the second constraint. Thus the goal is to prove there is some ${y}$ so that

$\displaystyle (4(ty+1)+1, t) = 1.$

But this is false. Note that if ${5}$ divides ${t}$ then

$\displaystyle 4(ty+1)+1 = 4ty + 5$

and so ${4x+1}$ is always divisible by ${5}$ . Ooops.

My next idea was to set ${x}$ to a more “clever” value. I tried

$\displaystyle x = ty + d.$

Here I thought that I could make ${d}$ special and control the situation. Now

$\displaystyle 4(ty+d)+1 = 4ty + 4d+1.$

This looked promising. I then said to myself that why not make ${4d+1}$ a large prime ${p}$ . Then clearly

$\displaystyle 4x + 1 = (4t)y + p.$

Since ${4t}$ and ${p}$ are relatively prime by the famous Dirichlet’s Theorem on arithmetic progressions we could make ${4x+1}$ a prime too by selecting ${y}$ . This would satisfy the second constraint, and we are done.

Not quite. The trouble is that we need to have also that

$\displaystyle (x,t) = 1.$

Now this is

$\displaystyle (ty + d, t) = 1.$

The trouble is that ${d}$ might not be relatively prime to ${t}$ . So we could just ${\dots}$ This seems like a recursion and I realized that it might not work.

The Problem’s Solution

I finally found a solution thanks to Delta Airlines. My dear wife, Kathryn Farley, and I were stuck in DC for several hours waiting for our delayed flight home. This time was needed for me to find a solution.

The key for me was to think about the value ${t}$ . It is usually a good idea to look at the simplest case first. So suppose that ${t=1}$ , then clearly the constraints

$\displaystyle (x,t) = 1 \text{ and } (4x+1,t) = 1,$

are now trivial. The next simplest case seems to be when ${t}$ is a prime. Let’s try ${t=3}$ . Now ${x=1}$ works. Let’s generalize this to any prime ${t>3}$ . The trick is to set ${x}$ so that

$\displaystyle x \equiv 2 \bmod t.$

Then ${4x+1}$ is equal to ${9}$ modulo ${t}$ , which is not divisible by ${t}$ . This shows that when ${t}$ is an odd prime there is always some ${x}$ .

Okay how do we get the full result? What if ${t}$ is the product of several primes? The Chinese remainder theorem to the rescue. Suppose that ${t}$ is divisible by the distinct odd primes ${p_{1},p_{2}, \dots, p_{m}}$ . We can easily see that we do not care if there are repeated factors, since that cannot change the relatively prime constraints.

Then we constraint ${x}$ by:

$\displaystyle x \equiv 1 \bmod 3$

and

$\displaystyle x \equiv 2 \bmod p_{k}$

for all primes ${p_{k}>3}$ . Then the Chinese remainder theorem proves there is some ${x}$ . Done.

Open Problems

Is there some one line proof of the problem? Do you know any references? There are several obvious generalizations of this simple problem, perhaps someone might look into them.