Proof - Odd composite numbers (3 of 3: By contradiction)

[dertyp]

back in school I hated math... you, sir, among others, reignited my interest in the subject by explaining things so well and clearly that it's really easy to follow and I'm not even an native English speaker. you really have a way with words. Keep up the good work. I'm sure you are inspiring lots of people out there. Thank you. I really mean it.

[orubla]

Great teachers are so easy to follow. Good vid.

[zaphrode]

one of the best teachers
explanations are so succinct

[sansh]

You are best math teacher in this world woo sir ❤️

[sendodo]

What if 4n-1 has a factor of the form 4m-1, but that factor is a composite number? Since the question says that it needs to have a prime factor in the form 4m-1, should we do extra steps to show that that number is prime as well?

[particleonazock]

Can you do truth trees? I like them as an effective means of solving knights and knaves and other propositional logic problems. Vry good tools for discrete mathematics.

[ryang]

Eddie's proof contains several logical errors (negating the given claim wrongly; using Part(a) wrongly by mistaking P⇒Q for its converse Q⇒P; most egregiously, proving the *weaker* claim "....must have at least one factor..." instead of the given, *stronger* claim "....must have at least one _prime_ factor..."). Here's a more rigorous presentation:

[ Let p be a composite number, suppose that it is of the form 4m-1, and *_assume_* that it has no prime factor of the form 4n-1.

Now, p, being of the form 4m-1, is odd, so its prime factorisation contains only odd numbers, so either it has a prime factor of the form 4n-1 or, by Part (a), its prime factors are all of the form 4n+1. The latter, by Part (b), is false; thus, p must have a prime factor of the form 4n-1. This *contradicts* our assumption; therefore, p _has_ a prime factor of the form 4n-1.

Hence, every composite number of the form 4m-1 has a prime factor of the form 4n-1. ]


PS. For reference, this is my previous proof, which is invalid because ∀n[P(n) or Q(n)] of course doesn't imply [∀nP(n) or ∀nQ(n)] (the converse is true though; thanks to Oisin Carroll for highlighting this crucial error):

[ Let m be a positive integer, suppose that 4m-1 is composite, and *assume* that for each n, 4n-1 is non-prime or not a factor of 4m-1.

Now, 4m-1 is odd, so must be a product of two odd numbers, so either has some factor 4k-1 or, by Part (a), equals (4p+1)(4q+1) for some p & q. The latter, by Part (b), is false; thus, some some 4k-1 must be a factor of 4m-1, i.e., it is false that for each k, 4k-1 is not a factor of 4m-1.

Therefore—continuing from the first paragraph—for each n, 4n-1 is non-prime; in particular, 4(1)-1=3 is non-prime; this is a *contradiction*; therefore, our assumption must be false; i.e., for some n, 4n-1 is a prime factor of 4m-1.

Hence, for each positive integer m, if 4m-1 is composite, then there is some n for which 4n-1 is its prime factor, as required.]

[geza]

Gday Eddie how are ya champ? I've personally quite exquisite

[oisincarroll]

I've really enjoyed these, I'm not sure I agree with some logic here. k could be a product of the form (4n-1)(4n+1) which would still satisfy the negation as long as 4n-1 is not prime (i.e. is composite). The full proof would need to contain some recursive logic to further factor (4n-1) as (4s-1)(4s+1) etc, and see you can't factor indefinately and reach some contradiction there... Maybe.

[shahadkftarawneh]

#GazaUnderAttack
#SaveAlAqsa
#FreePalestine
#IsraeliCrimes

[tadejsivic]

This proof is a bit meh. Too many words...
Still interesting, at least.

[c-math]

Everything is great, but the posture of your neck while you’re writing on ipad is totally wrong