Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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


(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).

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
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?

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.