LinkBack URL
About LinkBacksHi,
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.
[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.
I do this one.Originally Posted by R.Laramee
Note the number is not even, so its prime factors are all odd. Hence they have the form $\displaystyle 4k+1\mbox{ or }4k+3$. Note that if all prime factors had the form $\displaystyle 4k+1$ then their overall product also have the same form. Which is impossible because the number has the form $\displaystyle 4k+3$. This means at least of these prime factors must have the form $\displaystyle 4k+3$.
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
  |
