This site is supported by donations to The OEIS Foundation.

Template:Lemma

From OeisWiki
Jump to: navigation, search

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
ub   ≡   vb  (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
pQ
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)

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

  1. Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 6, Theorem 5.1
  2. To do: add statement.
  3. Needs proof.
  4. To do: further templates to do.