This site is supported by donations to The OEIS Foundation.

# Template:Lemma/doc

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
 n   ≥   2
and an integer
 b
coprime to
 n
, the congruence
 b φ (n)   ≡   1  (mod n)
, where
 φ (n)
is Euler’s totient function, holds.

Proof. Consider the
 φ (n)
numbers
 {b, a2  b, a3  b, ..., aφ (n)  b}
, where
 {1, a2, a3, ..., aφ (n)}
are the integers coprime to
 n
(i.e. the totatives of
 n
). Those are all different and nonzero
 (mod n)
, since
 b
is coprime to
 n
. Indeed, if
 u b   ≡   v b  (mod n)
, then
 u   ≡   v  (mod n)
, since we can “cancel the
 b
” (
 b
being coprime to
 n
). So we have
 φ (n)
numbers, all different, and none of them is
 0  (mod n)
. So they must be congruent to
 1, a2, a3, ..., aφ (n),
in some order. Multiplying them together, we get
 P = Πφ(n) b φ (n)
, where
 Πφ(n)
is the coprimorial of
 n
. So their product is congruent to
 Πφ(n)  (mod n)
. We now have two expressions for this product, so we can equate them:
 Πφ(n) b φ (n)   ≡   Πφ(n)  (mod n)
. Now
 Πφ(n)
is coprime to
 n
, so we can again cancel, to give
 b φ (n)   ≡   1  (mod n)
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. (EuclidBolker)

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
 Q
of
 ℙ
which exhausts
 ℙ
. Let’s designate the elements of the non-empty subset
 Q
as
 q1, ..., q| Q |
, then compute
m = 1 +
 | Q |

 i  = 1
qi
. The “fundamental theorem of arithmetic” implies that there is a prime
 p
which divides
 m
. Since no
 qi
divides
 m
, it follows that
 p ∉ Q
and
 Q   ≠   ℙ
. 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)

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>