4
$\begingroup$

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

  • 0
    All of you guys commenting that his contradiction assumption is false have not read the fifth number he wrote.2011-09-17

2 Answers 2

4

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.

  • 0
    ouch. this is bad to have overlooked :S Thanks2011-09-16
4

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?

  • 0
    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 haha2011-09-16