# What's wrong with my proof of infinitely many primes of the form $am+b$, $\gcd(a, b) = 1$

So the prof said in class that the proof of this is hard, but we might want to attempt at home. I won't be able to see him again until Wednesday, but I'm guessing there is some hole in my proof, since it didn't take me very long. Tough I can't tell what the problem is.

I hope it's not sloppy to read. I've never written a long proof with the intent of it being read before.

THEOREM

For all integers $a, b, m$ and $GCD(a, b) = 1$, there are infinitely many primes of the form $am + b$

PROOF

(Let $a, b, c, n_i$ be integers)

By contradiction, let us assume our theorem to be false.

1. Then it follows that there exist two integers $a, b$, where $GCD(a, b) = 1$, such that, for all $m$,

$\displaystyle \frac{am + b}{c} = n_1$

That is, $c | am + b$.

For some $c$ and some $n_1$. ( The value of $c$ and $n_1$ changing as the value of $m$ changes.)

2. Since $a$ and $b$ have no factors in common, it follows that:

$\displaystyle \frac{m}{c} + \frac{b}{c} = n_2$

(That is, that $GCD(m, b) > 1$ in order for Equality 1 to hold, and thus, both are divisible by some $c$.)

3. But this contradicts (1.) in the following way:

It is clear that, for some set of primes $\{ p_{b1}...p_{bk} \}$, $b = p_{b1} p_{b2} ... c ... p_{bk}$.

But suppose an $m > b$ such that

$m = p_{m1} p_{m2} ... p_{mq}$, and

$\{p_{b1}...p_{bk}\} \cap \{p_{m1}...p_{mq}\} = \emptyset$

For example: $m = p_{bk+1}$

Clearly, not all $m$'s have a common factor with $b$.

4. From this it follows that there must be at least one integer $m$ for which $am + b$ is prime.

5. Proving there are infinitely many more is possible once this single case is found (this part we did in class, so I won't write it).

-
Your first step is incorrect. You didn't negate the quantifiers correctly. –  Qiaochu Yuan Sep 16 '11 at 22:02
If there is an am+b that never yields a prime, doesn't it follow that (am+b) are always divisible by some number? (not necessarily the same number) –  iDontKnowBetter Sep 16 '11 at 22:05
The negation of the statement isn’t that $am+b$ never yields a prime: it’s that it yields only finitely many primes. This is equivalent to saying that there is some $m_0$ such that $am+b$ is composite for all $m\ge m_0$ (but not necessarily for all $m$). –  Brian M. Scott Sep 16 '11 at 22:12
HINT $\:$ not infinite means finite, which generally is not equivalent to zero. –  Bill Dubuque Sep 16 '11 at 22:13
For all integers $a$, $b$, $m$ and $GCD(a, b) = 1$, there are infinitely many primes of the form $am + b$. Is this written correctly? Shouldn't it read: There are infinitely many primes $p$ such that there exist $a$, $b$, $m$ for which $GCD(a, b) = 1$ and $p = am + b$. –  Giorgio Sep 17 '11 at 1:01

Qiaochu’s answer addresses the problem with your first step. The problem with the second step can be seen from a simple example. If $a=2$, $b=3$, and $m=11$, then $a$ and $b$ are relatively prime, $am+b= 2\cdot 11 + 3 = 25 = 5^2$ is composite, and yet $m$ and $b$ have no common factor greater than $1$: they are relatively prime. It’s true that if $am+b$ is composite, it must have a non-trivial factor $c$, and it’s also true that $c$ cannot divide both $a$ and $b$, but as my example shows, it needn’t divide either of $a$ and $b$: it can come out of thin air, so to speak, as $5$ did in the example.

It’s good to bear in mind that the sum of two integers can have factors that are completely unrelated to any factors of the original integers.

-
ouch. this is bad to have overlooked :S Thanks –  iDontKnowBetter Sep 16 '11 at 22:26

The theorem you want to prove is

For all positive integers $a, b$ such that $\gcd(a, b) = 1$, there exist infinitely many $m$ such that $am + b$ is prime.

If you want to proceed by contradiction, the negation of this statement is

There exist positive integers $a, b$ such that $\gcd(a, b) = 1$ and such that, for all but finitely many $m$, the number $am + b$ is composite.

Can you see how this is not equivalent to what you wrote?

-
If I then also show that, if there exists one case such that am+b is prime, then there exist infinitely many, would that resolve this issue? Thanks. –  iDontKnowBetter Sep 16 '11 at 22:29
@fakaff: well, that's a reasonably well-known reduction. But that's not the mistake I'm pointing out. –  Qiaochu Yuan Sep 16 '11 at 22:50
Got it. I was asking as an aside; of trying it that way instead of by contradiction because I want to try again in a better way. Overlooking my mistake in step 2 I feel kinda dumb haha –  iDontKnowBetter Sep 16 '11 at 23:12