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. 


*

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

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

*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$.

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

*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).
 A: 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? 
A: 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.
