[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/prime.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "prime" type: concept related: [Divide, Number, Integer, Prime] source: https://www.jemoka.com/posts/kbhprime/ confidence: high status: active --- An integer \(p > 1\) is prime if it has no positive divisors other than \(1\) and itself. No even number, except \(2\), is prime. Because 2 additional information There are infinitely many primes Credit: Euler. Proof: Assume to the contrary that there are finitely many primes. \(p_1, …, p_{n}\). We desire to make a new prime to reach contradiction. Consider: \begin{equation} N = p_1 \times \dots \times p_{n} + 1 \end{equation} Note that \(p_1 \times … \times p_{n}\) is divisible by each of the \(p_{j}\). If some \(p_i |N\), \(p_{i}|1\), which is impossible as \(1\) is not divisible by anything. So, no \(p_{i}\) divides \(N\). If \(N\) is now prime, we are done as it is not in the list of \(p_{j}\). If not, pick any prime divisor \(p\) of \(N\). We will note that given no \(p_{j}\) divides \(N\), therefore any prime divisor is a new prime. Having made a new prime, we reach contradiction. \(\blacksquare\) coprime Two integers \(a, b\) is considered coprime if \(\gcd (a,b) = 1\). Therefore, because greatest common divisor is a linear combination