The {{proved statement}} OEIS Wiki utility template is used by the templates
and allows for a consistent presentation of propositions, lemmas, theorems and corollaries throughout OEIS Wiki. It also provides a categorization of the article into either
Usage
- {{Proved statement|class = class|ID = ID|name = name|author = author|year = year|statement = statement|proof = proof}}
where
- class is the class (of the proved statement), i.e. Proposition (default), Lemma, Theorem and Corollary;
- ID is an optional ID (e.g. P1) which can also be used as an anchor by preceding it with the class (e.g. #Proposition P1);
- name is the optional name of the proposition/lemma/theorem/corollary (e.g. Pythagorean theorem);
- author (or authors) is the optional (but recommended) name (or names) of the person/group (or persons/groups) who proved the proposition/lemma/theorem/corollary (e.g. Pythagoras);
- year is the optional year of publication for the proof of the proposition/lemma/theorem/corollary (e.g. 1763);
- statement is the statement of the proposition/lemma/theorem/corollary;
- proof is the proof of the proposition/lemma/theorem/corollary (the Halmos, i.e. □, is automatically appended to the proof).
Examples
'''Euler{{'}}s theorem''' pertains to (...)
{{Proved statement
| class = Theorem
| ID = T1
| name = Euler{{'}}s theorem
| author = [[Leonhard Euler|Euler]]
| year = 1763
| statement =
Given an integer {{math|''n'' {{rel|ge}} 2|tex = n \ge 2|&}} and an integer {{math|''b''|tex = b|&}} [[coprime]] to {{math|''n''|tex = n|&}}, the [[congruence]] {{math|''b''{{^|''{{Gr|varphi}}''{{sp|1}}(''n'')}} {{rel|equiv}} 1 {{pmod|''n''}}|tex = b^{\varphi(n)} \equiv 1 \pmod{n}|&}}, where {{math|''{{Gr|varphi}}''{{sp|1}}(''n'')|tex = \varphi(n)|&}} is [[Euler's totient function|Euler{{'}}s totient function]], holds.
| proof =
Consider the {{math|''{{Gr|varphi}}''{{sp|1}}(''n'')|tex = \varphi(n)|&}} numbers {{math|{{set|''b'', ''a''{{sub|2}}{{sp|2}}''b'', ''a''{{sub|3}}{{sp|2}}''b'', ..., ''a''{{sub|''{{Gr|varphi}}''{{sp|1}}(''n'')}}{{sp|2}}''b''}}|tex = \{ b, a_2 b, a_3 b, \ldots, a_{\varphi(n)} b \}|&}}, where {{math|{{set|1, ''a''{{sub|2}}, ''a''{{sub|3}}, ..., ''a''{{sub|''{{Gr|varphi}}''{{sp|1}}(''n'')}}}}|tex = \{ 1, a_2, a_3, \ldots, a_{\varphi(n)} \}|&}} are the integers coprime to {{math|''n''|tex = n|&}} (i.e. the [[totatives]] of {{math|''n''|tex = n|&}}). Those are all different and nonzero {{math|{{pmod|''n''}}|tex = \pmod{n}|&}}, since {{math|''b''|tex = b|&}} is coprime to {{math|''n''|tex = n|&}}. Indeed, if {{math|''u''{{sp|1}}''b'' {{rel|equiv}} ''v''{{sp|1}}''b'' {{pmod|''n''}}|tex = u b \equiv v b \pmod{n}|&}}, then {{math|''u'' {{rel|equiv}} ''v'' {{pmod|''n''}}|tex = u \equiv v \pmod{n}|&}}, since we can “cancel the {{math|''b''|tex = b|&}}” ({{math|''b''|tex = b|&}} being coprime to {{math|''n''|tex = n|&}}). So we have {{math|''{{Gr|varphi}}''{{sp|1}}(''n'')|tex = \varphi(n)|&}} numbers, all different, and none of them is {{math|0 {{pmod|''n''}}|tex = 0 \pmod{n}|&}}. So they must be congruent to {{math|1, ''a''{{sub|2}}, ''a''{{sub|3}}, ..., ''a''{{sub|''{{Gr|varphi}}''{{sp|1}}(''n'')}},|tex = 1, a_2, a_3, \ldots, a_{\varphi(n)},|&}} in some order. Multiplying them together, we get {{math|''P'' {{=}} {{Gr|Pi}}{{sub|''{{Gr|varphi}}''}}(''n'') ''b''{{^|''{{Gr|varphi}}''{{sp|1}}(''n'')}}|tex = P = \Pi_{\varphi}(n) \, b^{\varphi(n)}|&}}, where {{math|{{Gr|Pi}}{{sub|''{{Gr|varphi}}''}}(''n'')|tex = \Pi_{\varphi}(n)|&}} is the [[coprimorial]] of {{math|''n''|tex = n|&}}. So their product is congruent to {{math|{{Gr|Pi}}{{sub|''{{Gr|varphi}}''}}(''n'') {{pmod|''n''}}|tex = \Pi_{\varphi}(n) \pmod{n}|&}}.
We now have two expressions for this product, so we can equate them: {{math|{{Gr|Pi}}{{sub|''{{Gr|varphi}}''}}(''n'') ''b''{{^|''{{Gr|varphi}}''{{sp|1}}(''n'')}} {{rel|equiv}} {{Gr|Pi}}{{sub|''{{Gr|varphi}}''}}(''n'') {{pmod|''n''}}|tex = \Pi_{\varphi}(n) \, b^{\varphi(n)} \equiv \Pi_{\varphi}(n) \pmod{n}|&}}. Now {{math|{{Gr|Pi}}{{sub|''{{Gr|varphi}}''}}(''n'')|tex = \Pi_{\varphi}(n)|&}} is coprime to {{math|''n''|tex = n|&}}, so we can again cancel, to give {{math|''b''{{^|''{{Gr|varphi}}''{{sp|1}}(''n'')}} {{rel|equiv}} 1 {{pmod|''n''}}|tex = b^{\varphi(n)} \equiv 1 \pmod{n}|&}}.
}}
[[Fermat's little theorem|Fermat{{'}}s little theorem]] is a special case of [[#Theorem T1|Euler{{'}}s theorem]] so that (...)
Euler’s theorem pertains to (...)
Theorem T1 (Euler’s theorem, 1763). (Euler)
Given an integer and an integer coprime to , the congruence , where is Euler’s totient function, holds.
Proof. Consider the numbers | {b, a2 b, a3 b, ..., aφ (n) b} |
, where are the integers coprime to (i.e. the totatives of ). Those are all different and nonzero , since is coprime to . Indeed, if , then , since we can “cancel the ” ( being coprime to ). So we have numbers, all different, and none of them is . So they must be congruent to in some order. Multiplying them together, we get , where is the coprimorial of . So their product is congruent to .
We now have two expressions for this product, so we can equate them: | Πφ(n) b φ (n) ≡ Πφ(n) (mod n) |
. Now is coprime to , so we can again cancel, to give . □
Fermat’s little theorem is a special case of
Euler’s theorem so that (...)
{{Theorem
| authors = [[Euclid]]–[[Ethan D. Bolker|Bolker]]
| statement = There are infinitely many [[Prime numbers|primes]].
| proof =
Designate by {{math|{{mathbb|P}}|tex = \mathbb{P}|&}} the set of all prime numbers. Since {{mathfont|2}} is prime, {{math|{{mathbb|P}}|tex = \mathbb{P}|&}} is not the [[empty set]]. We will now demonstrate that there is no finite subset {{math|''Q''|tex = Q|&}} of {{math|{{mathbb|P}}|tex = \mathbb{P}|&}} which exhausts {{math|{{mathbb|P}}|tex = \mathbb{P}|&}}. Let{{'}}s designate the elements of the non-empty subset {{math|''Q''|tex = Q|&}} as {{math|''q''{{sub|1}}, ..., ''q''{{sub|{{card|''Q''}}}}|tex = q_1, \ldots, q_{ {{card|Q|tex}} }|&}}, then compute {{math|''m'' {{=}} 1 + {{prod|''i''{{=}}1|{{card|''Q''}}}} ''q''{{sub|''i''}}{{sp|1}}|tex = m = 1 + \prod_{i=1}^{ {{card|Q|tex}} } q_i|&}}. The {{"|[[fundamental theorem of arithmetic]]|"}} implies that there is a prime {{math|''p''|tex = p|&}} which divides {{math|''m''|tex = m|&}}. Since no {{math|''q''{{sub|''i''}}|tex = q_i|&}} divides {{math|''m''|tex = m|&}}, it follows that {{math|''p'' {{sym|notin}} ''Q''|tex = p \notin Q|&}} and {{math|''Q'' {{rel|neq}} {{mathbb|P}}|tex = Q \neq \mathbb{P}|&}}. Therefore, {{math|{{mathbb|P}}|tex = \mathbb{P}|&}} is infinite.<ref>Ethan D. Bolker, ''Elementary Number Theory: An Algebraic Approach''. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 6, Theorem 5.1</ref>
}}
Theorem. (Euclid–Bolker)
There are infinitely many primes.
Proof. Designate by the set of all prime numbers. Since 2 is prime, is not the empty set. We will now demonstrate that there is no finite subset of which exhausts . Let’s designate the elements of the non-empty subset as , then compute . The “fundamental theorem of arithmetic” implies that there is a prime which divides . Since no divides , it follows that and . Therefore, is infinite.[1] □
Example with default class
{{Proved statement
| class =
| ID = P1
| name = Some proved statement name
| author = Some author
| year =
| statement =
| proof =
}}
Proposition P1 (Some proved statement name). (Some author)
STATEMENT REQUIRED! (add statement) [2]
Proof. PROOF GOES HERE. □ (Provide proof: PROOF GOES HERE. □) [3]
Example for proposition
{{Proposition
| ID = P1
| name = Some proposition name
| author = Some author
| statement =
Proposition statement.
| proof =
Proposition proof.
}}
Proposition P1 (Some proposition name). (Some author)
Proposition statement.
Proof. Proposition proof. □
Example for lemma
{{Lemma
| ID = L1
| name = Some lemma name
| author = Some author
| statement =
Lemma statement.
| proof =
Lemma proof.
}}
Lemma L1 (Some lemma name). (Some author)
Lemma statement.
Proof. Lemma proof. □
Example for theorem
{{Theorem
| ID = T1
| name = Some theorem name
| author = Some author
| statement =
Theorem statement.
| proof =
Theorem proof.
}}
Theorem T1 (Some theorem name). (Some author)
Theorem statement.
Proof. Theorem proof. □
Example for corollary
{{Corollary
| ID = C1
| name = Some corollary name
| author = Some author
| statement =
Corollary statement.
| proof =
Corollary proof.
}}
Corollary C1 (Some corollary name). (Some author)
Corollary statement.
Proof. Corollary proof. □
Code
Further templates to do (further templates to do) [4] (no proof is involved in those): algorithm, principle, law, postulate, axiom, definition, notation.
<noinclude>{{Documentation}}</noinclude><includeonly><!--
Templates using this template: proposition, lemma, theorem, corollary
Further templates to do (no proof is involved in those): algorithm, conjecture, hypothesis, thesis, principle, law, definition, notation
--><blockquote class="{{#if: {{{class|}}} | {{lc: {{{class}}} }} | proposition }}" <!--
-->id="{{#if: {{{ID|}}} | {{#if: {{{class|}}} | {{ucfirst: {{lc: {{{class}}} }} }} | Proposition }} {{{ID}}} }}"><!--
-->'''{{#if: {{{class|}}} | {{ucfirst: {{lc: {{{class}}} }} }} | Proposition }}<!--
-->{{#if: {{{ID|}}} | {{{ID}}} }}{{#if: {{{name|}}} | ({{{name}}}{{#if: {{{year|}}} | , {{{year}}} }}) }}.'''<!--
-->{{#if: {{{author|}}} | ''({{{author|}}})'' }}<!--
-->{{#if: {{{authors|}}} | ''({{{authors|}}})'' }}<!--
-->{{nl|2}}{{#if: {{{statement|}}} | {{{statement}}} | STATEMENT REQUIRED!{{To do|add statement}} }}<!--
-->{{nl|2}}''Proof.'' {{#if: {{{proof|}}} | {{{proof}}} □ | PROOF GOES HERE. □{{To do|prove}} }}
</blockquote><!--
-->{{#switch: {{#if: {{{class|}}} | {{lc: {{{class}}} }} | proposition }}
| corollary = [[Category:Articles containing corollaries]]
| lemma = [[Category:Articles containing lemmas]]
| proposition = [[Category:Articles containing propositions]]
| theorem = [[Category:Articles containing theorems]]
}}</includeonly>
See also
Notes
- ↑ Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 6, Theorem 5.1
- ↑ To do: add statement.
- ↑ Needs proof.
- ↑ To do: further templates to do.
