# Thread: [SOLVED] Proof of divisibility

1. ## [SOLVED] Proof of divisibility

Hi,
I am having difficulty with some proofs.

Show that every composite integer of the form 4n+3 has a factor of the form 4m+3.

and

Show that every composite integer of the form 6n+5 has a factor of the form 6m+5.

2. Originally Posted by R.Laramee
Hi,
I am having difficulty with some proofs.

Show that every composite integer of the form 4n+3 has a factor of the form 4m+3.
I do this one.

Note the number is not even, so its prime factors are all odd. Hence they have the form $4k+1\mbox{ or }4k+3$. Note that if all prime factors had the form $4k+1$ then their overall product also have the same form. Which is impossible because the number has the form $4k+3$. This means at least of these prime factors must have the form $4k+3$.

3. Originally Posted by R.Laramee
Hi,
I am having difficulty with some proofs.

Show that every composite integer of the form 4n+3 has a factor of the form 4m+3.

and

Show that every composite integer of the form 6n+5 has a factor of the form 6m+5.
Suppose x is composite and of the form 4n+3, and let a and b be such that
ab=x. Then a is of the form 4m, 4m+1 or 4m+2 for some m, and b is of the
form 4k, 4k+1, or 4k+2. But then ab is not of the form 4n+3, a contradiction.

RonL