SOLUTION: Hi guys, this is a proofing type question. There are three parts - I don't know how to answer the last one. Part 1 and 2 should help with the final part. They are summarised bel

Algebra ->  Expressions-with-variables -> SOLUTION: Hi guys, this is a proofing type question. There are three parts - I don't know how to answer the last one. Part 1 and 2 should help with the final part. They are summarised bel      Log On


   

Question 1172305: Hi guys, this is a proofing type question.
There are three parts - I don't know how to answer the last one. Part 1 and 2 should help with the final part. They are summarised below.
Every odd number is one more or one less than a multiple of 4
and
The product of any two positive integers of the form 4n%2B1, n is positive integer, is also of the form 4n%2B1.
The actual question is:
Hence, prove by contradiction that any composite number of the form 4n-1 must have at least one prime factor of the form 4n-1.
Answer by ikleyn(52794) About Me  (Show Source):
You can put this solution on YOUR website!
.

So, the statement, which you want to prove, is THIS


   +------------------------------------------------------------------------+
   |  prove by contradiction that any composite number of the form (4n-1)   |
   |  must have at least one prime factor of the form (4n-1).               |
   +------------------------------------------------------------------------+



Let N be a composite number of the form (4n-1).


Then it is a product of the odd prime numbers; the prime number 2 is not its divisor.


Let assume that all its prime divisors are of the form (4n+1).


Notice that the product of any two odd numbers of the form (4n+1) is the number of the form (4n+1).
 


    It can be proven by direct multiplication of the numbers of this form.



It implies that a product of ANY number of the primes of the form (4n+1) has the form (4n+1).


But our number N has the form (4n-1).


So, we got a CONTRADICTION, which proves the statement.

The proof is completed.