43. Every number has a prime factor

HardProofAcademy Pass40 points

Prove that every k ≥ 2 has a prime factor, using the definition of Prime above the editor. Like every problem here it is Mathlib-free: only Lean’s core library is available.

Ordinary induction does not work: the factor of k comes from a divisor of k, not from k - 1. You need strong induction, where the hypothesis covers every smaller number.

This is the key lemma of problem 42, “Infinitely many primes”.

Without the Pass you can run 3 Pass problems against their examples. Submitting, the hints and the editorial come with the Academy Pass. The daily problem and one Medium problem a week are open to every account.

Solution.lean
1def Prime (p : Nat) : Prop := 2 ≤ p ∧ ∀ m, m ∣ p → m = 1 ∨ m = p
2theorem solution (k : Nat) (hk : 2 ≤ k) : ∃ p, Prime p ∧ p ∣ k := by
given
Loading editor…

Where you start. Everything above ⊢ may be assumed; the line below it is what you must prove.

k:Nat
hk:2 ≤ k
⊢∃ p, Prime p ∧ p ∣ k
ReadyLn 1, Col 1Lean 4
Draft saved in this browser