Lesson Composite number of the form (4n+3) must have a prime divisor of the form (4n+3)

This Lesson (Composite number of the form (4n+3) must have a prime divisor of the form (4n+3)) was created by by ikleyn(52908)

: View Source, Show
About ikleyn:

Composite number of the form (4n+3) must have a prime divisor of the form (4n+3)

Problem 1

Prove that any composite number of the form (4n+3) must have at least one prime factor of the form (4n+3).

Solution

Let N be a composite number of the form (4n+3).


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 easily 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+3).


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

The proof is completed.

My other lessons in this site on miscellaneous problems on divisibility of integer numbers are
    - Light flashes on a Christmas tree and a Least Common Multiple
    - The number that leaves a remainder 1 when divided by 2, by 3, by 4, by 5 and so on until 9
    - The number which gives remainder 4 when divided by 7, remainder 5 when divided by 8 and remainder 6 when divided by 9
    - Introductory problems on divisibility of integer numbers
    - Finding Greatest Common Divisor of integer numbers
    - Relatively prime numbers help to solve the problem
    - Solving equations in integer numbers
    - Quadratic polynomial with odd integer coefficients can not have a rational root
    - Proving an equation has no integer solutions
    - Problems on divisors of a given number
    - How many three-digit numbers are multiples of both 5 and 7?
    - How many 3-digit numbers are not divisible by 2; not divisible by 3; not divisible by either 2 or 3
    - How many integer numbers in the range 1-300 are divisible by at least one of the integers 4, 6 and 15 ?
    - Find the remainder of division
    - Why 3^n + 7^n - 2 is divisible by 8 for all positive integer n ?
    - What is the last digit of the number a^n ?
    - Find the last three digits of these numbers
    - Find the last two digits of the number 3^123 + 7^123 + 9^123
    - Find the last two digits of (1! + 2! + 3! + ... + 2024!)^2024
    - Find n-th term of a sequence
    - Find n-th term of a sequence
    - Solving Diophantine equations
    - How many integers of the form n^2 + 18n + 13 are perfect squares
    - Miscellaneous problems on divisibility numbers
    - Find the sum of digits of integer numbers
    - Two-digit numbers with digit "9"
    - Find a triangle with integer side lengths and integer area
    - Math circle level problem on the hundred-handed monster Briareus
    - Math Circle level problem on lockers and divisors of integer numbers
    - Nice entertainment problems related to divisibility property
    - Solving problems on modular arithmetic
    - Using the little Fermat's theorem to solve a problem on modular arithmetic
    - OVERVIEW of miscellaneous solved problems on divisibility of integer numbers

This lesson has been accessed 1682 times.