Chinesischer Restsatz

Chinesischer Restsatz (auch chinesischer Restklassensatz genannt) ist der Name mehrerer ähnlicher Theoreme der abstrakten Algebra und Zahlentheorie.

Simultane Kongruenzen ganzer Zahlen

Eine simultane Kongruenz ganzer Zahlen ist ein System von linearen Kongruenzen

<math>

\begin{matrix} x & \equiv & a_1 & \pmod{m_1} \\ x & \equiv & a_2 & \pmod{m_2} \\

 & \vdots &     &            \\

x & \equiv & a_n & \pmod{m_n} \\ \end{matrix} </math>

für die alle <math>x</math> bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung <math>x_0</math> existiert, dann sind mit <math>M := \operatorname{kgV}(m_1, m_2, m_3, \ldots, m_n)</math> die Zahlen <math>x_0 + kM \ (k \in \mathbb{Z})</math> genau alle Lösungen, wobei <math>\operatorname{kgV}</math> für das kleinste gemeinsame Vielfache steht. Es kann aber auch sein, dass es gar keine Lösung gibt.

Teilerfremde Moduln

Herleitung

Die Originalform des chinesischen Restsatzes stammt aus dem Buch Sūn Zǐ Suànjīng ({{#ifeq: {{#if:{{#invoke:TemplUtl|faculty|}}|0}}|0||{{#ifeq: Chinesischer Restsatz | Chinesische Schrift | chinesisch | chinesisch}} }}{{#if: 孫子算經

 | {{#invoke:Vorlage:lang|flat}}{{#if: 孙子算经
 |  /

}}}}{{#if: 孙子算经

 | {{#invoke:Vorlage:lang|flat}}

|{{#if: 孫子算經|

 | {{#invoke:Vorlage:lang|flat}}

}}}}{{#if:

 | , {{#ifeq: {{#if:{{#invoke:TemplUtl|faculty|}}|0}}|0||{{#ifeq: Chinesischer Restsatz | Pinyin | Pinyin | Pinyin
   }}}} {{#if: 
   |{{#ifeq: 1 | 0
    | {{#if: {{{hcaudio}}}

| {{#ifexist: Media:{{{hcaudio}}}

   | Vorlage:CodexIcon{{#ifeq: 0 | 1 | ^{Vorlage:CodexIcon}}}
   | !?! [[:Datei:{{{hcaudio}}}]] fehlt}}

| }} [[Media:{{{hcaudio}}}|{{#invoke:Vorlage:lang|flat}}]]^{?/[[:Datei:{{{hcaudio}}}|ⓘ]]}

    | <phonos file="{{{hcaudio}}}">{{#invoke:Vorlage:lang|flat}}</phonos>^/?

}}

   |{{#invoke:Vorlage:lang|flat}}
   }}

|{{#if:

 | {{#ifeq: 1 | 0
    | {{#if: {{{hcaudio}}}

| {{#ifexist: Media:{{{hcaudio}}}

   | Vorlage:CodexIcon{{#ifeq: 0 | 1 | ^{Vorlage:CodexIcon}}}
   | !?! [[:Datei:{{{hcaudio}}}]] fehlt}}

| }} [[Media:{{{hcaudio}}}|anhören (hochchinesisch)]]^{?/[[:Datei:{{{hcaudio}}}|ⓘ]]}

    | <phonos file="{{{hcaudio}}}">anhören (hochchinesisch)</phonos>^/?

}} }}}}{{#if:

 | , IPA (hochchinesisch) <templatestyles src="IPA/styles.css" />{{#if:|[}}[{{{hcipa}}}]{{#if:
    | ] <phonos file="{{{Tondatei}}}"></phonos>
  }}{{#invoke:TemplatePar|check

|all= 1= |opt= 2= Tondatei= |template=Vorlage:IPA |errNS= 0 |cat=Wikipedia:Vorlagenfehler/Vorlage:IPA |format=@@@ }} }}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Tongyong Pinyin | Tongyong Pinyin | Tongyong Pinyin}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: {{#if:{{#invoke:TemplUtl|faculty|}}|0}}|0||{{#ifeq: Chinesischer Restsatz | Wade-Giles | W.-G. | W.-G.}}}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Zhuyin | Zhuyin | Zhuyin}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Gwoyeu Romatzyh | G. R. | G. R.}} {{{g}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Hokkien | Hokkien | Hokkien}} {{{ho}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Nanjing | Nanjing | Nanjing-Mandarin}} {{{lj}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Xiang | Xiang | Xiang}} {{{hsn}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Hakka (Sprache) | Hakka | Hakka}} {{{hk}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Jyutping | Jyutping | Jyutping}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Yale-Romanisierung | Yale | Yale}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Kantonesische Sprache | kant. | kantonesisch
   }} {{#if: 
   | {{#ifeq: 1 | 0
    | {{#if: {{{kaudio}}}

| {{#ifexist: Media:{{{kaudio}}}

   | Vorlage:CodexIcon{{#ifeq: 0 | 1 | ^{Vorlage:CodexIcon}}}
   | !?! [[:Datei:{{{kaudio}}}]] fehlt}}

| }} [[Media:{{{kaudio}}}|{{{k}}}]]^{?/[[:Datei:{{{kaudio}}}|ⓘ]]}

    | <phonos file="{{{kaudio}}}">{{{k}}}</phonos>^/?

}}

   | {{{k}}}
   }}

|{{#if:

 | {{#ifeq: 1 | 0
    | {{#if: {{{kaudio}}}

| {{#ifexist: Media:{{{kaudio}}}

   | Vorlage:CodexIcon{{#ifeq: 0 | 1 | ^{Vorlage:CodexIcon}}}
   | !?! [[:Datei:{{{kaudio}}}]] fehlt}}

| }} [[Media:{{{kaudio}}}|anhören (kantonesisch)]]^{?/[[:Datei:{{{kaudio}}}|ⓘ]]}

    | <phonos file="{{{kaudio}}}">anhören (kantonesisch)</phonos>^/?

}} }}}}{{#if:

 | , IPA (kantonesisch) <templatestyles src="IPA/styles.css" />{{#if:|[}}[{{{kipa}}}]{{#if:
    | ] <phonos file="{{{Tondatei}}}"></phonos>
  }}{{#invoke:TemplatePar|check

|all= 1= |opt= 2= Tondatei= |template=Vorlage:IPA |errNS= 0 |cat=Wikipedia:Vorlagenfehler/Vorlage:IPA |format=@@@ }} }}{{#if:

 | , englisch {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Taiwanische Sprache | Pe̍h-ōe-jī |Pe̍h-ōe-jī}} {{{poj}}}

}}{{#if: Sun Zis Handbuch der Arithmetik

 | – „Sun Zis Handbuch der Arithmetik“

}}) des chinesischen Mathematikers Sun Zi (vermutlich 3. Jh.)<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}| |}}}}{{#if:J. J. O’Connor, E. F. Robertson|J. J. O’Connor, E. F. Robertson: }}{{#if:|{{#if:Sun Zi biography|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Sun Zi biography}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Sun Zi biography}}}}|[{{#invoke:URLutil|getNormalized|1=http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Sun Zi biography}}}}]}}{{#if:| ({{{format}}}{{#if:School of Mathematics and Statistics, University of St Andrews, Scotland{{#if: 2010-08-05 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html}}%7C%7C URL ungültig}}}}{{#if:Sun Zi biography|{{#if:{{#invoke:WLink|isValidLinktext|1=Sun Zi biography|lines=0}}|| Linktext ungültig}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: School of Mathematics and Statistics, University of St Andrews, Scotland| School of Mathematics and Statistics, University of St Andrews, Scotland{{#if: |,|{{#if: 2010-08-05 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2010-08-05 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2010-08-05 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:School of Mathematics and Statistics, University of St Andrews, Scotland|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}|{{{archiv-datum}}}{{#if:12612||(?)}}}}}}{{#if: 2010-08-05|;}}}}{{#if: 2010-08-05| {{#if:School of Mathematics and Statistics, University of St Andrews, Scotland{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2010-08-05 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2010-08-05|class=Zitationswartung}} }} {{#invoke:DateTime|format|2010-08-05|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:School of Mathematics and Statistics, University of St Andrews, Scotland{{#if: 2010-08-05 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2010-08-05 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}}

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html
      | {{#if:{{#invoke:URLutil|isWebURL|http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html
       | {{#if:{{#invoke:URLutil|isWebURL|http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html
      | {{#if:{{#invoke:URLutil|isWebURL|http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html
       | {{#if:{{#invoke:URLutil|isWebURL|http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref><ref>H. Gericke gibt als möglichen Entstehungszeitraum 280 bis 473 n. Chr. an. (H. Gericke: Mathematik in Antike, Orient und Abendland. Springer, Berlin 1990, Abschnitt 3.1, S. 182)</ref> und wurde 1247 von Qin Jiushaos Shùshū Jiǔzhāng ({{#ifeq: {{#if:{{#invoke:TemplUtl|faculty|1}}|1}}|1||{{#ifeq: Chinesischer Restsatz | Chinesische Schrift | chinesisch | chinesisch}} }}{{#if: 數書九章

 | {{#invoke:Vorlage:lang|flat}}{{#if: 数书九章
 |  /

}}}}{{#if: 数书九章

 | {{#invoke:Vorlage:lang|flat}}

|{{#if: 數書九章|

 | {{#invoke:Vorlage:lang|flat}}

}}}}{{#if:

 | , {{#ifeq: {{#if:{{#invoke:TemplUtl|faculty|1}}|1}}|1||{{#ifeq: Chinesischer Restsatz | Pinyin | Pinyin | Pinyin
   }}}} {{#if: 
   |{{#ifeq: 1 | 0
    | {{#if: {{{hcaudio}}}

| {{#ifexist: Media:{{{hcaudio}}}

   | Vorlage:CodexIcon{{#ifeq: 0 | 1 | ^{Vorlage:CodexIcon}}}
   | !?! [[:Datei:{{{hcaudio}}}]] fehlt}}

| }} [[Media:{{{hcaudio}}}|{{#invoke:Vorlage:lang|flat}}]]^{?/[[:Datei:{{{hcaudio}}}|ⓘ]]}

    | <phonos file="{{{hcaudio}}}">{{#invoke:Vorlage:lang|flat}}</phonos>^/?

}}

   |{{#invoke:Vorlage:lang|flat}}
   }}

|{{#if:

 | {{#ifeq: 1 | 0
    | {{#if: {{{hcaudio}}}

| {{#ifexist: Media:{{{hcaudio}}}

   | Vorlage:CodexIcon{{#ifeq: 0 | 1 | ^{Vorlage:CodexIcon}}}
   | !?! [[:Datei:{{{hcaudio}}}]] fehlt}}

| }} [[Media:{{{hcaudio}}}|anhören (hochchinesisch)]]^{?/[[:Datei:{{{hcaudio}}}|ⓘ]]}

    | <phonos file="{{{hcaudio}}}">anhören (hochchinesisch)</phonos>^/?

}} }}}}{{#if:

 | , IPA (hochchinesisch) <templatestyles src="IPA/styles.css" />{{#if:|[}}[{{{hcipa}}}]{{#if:
    | ] <phonos file="{{{Tondatei}}}"></phonos>
  }}{{#invoke:TemplatePar|check

|all= 1= |opt= 2= Tondatei= |template=Vorlage:IPA |errNS= 0 |cat=Wikipedia:Vorlagenfehler/Vorlage:IPA |format=@@@ }} }}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Tongyong Pinyin | Tongyong Pinyin | Tongyong Pinyin}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: {{#if:{{#invoke:TemplUtl|faculty|1}}|1}}|1||{{#ifeq: Chinesischer Restsatz | Wade-Giles | W.-G. | W.-G.}}}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Zhuyin | Zhuyin | Zhuyin}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Gwoyeu Romatzyh | G. R. | G. R.}} {{{g}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Hokkien | Hokkien | Hokkien}} {{{ho}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Nanjing | Nanjing | Nanjing-Mandarin}} {{{lj}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Xiang | Xiang | Xiang}} {{{hsn}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Hakka (Sprache) | Hakka | Hakka}} {{{hk}}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Jyutping | Jyutping | Jyutping}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Yale-Romanisierung | Yale | Yale}} {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Kantonesische Sprache | kant. | kantonesisch
   }} {{#if: 
   | {{#ifeq: 1 | 0
    | {{#if: {{{kaudio}}}

| {{#ifexist: Media:{{{kaudio}}}

   | Vorlage:CodexIcon{{#ifeq: 0 | 1 | ^{Vorlage:CodexIcon}}}
   | !?! [[:Datei:{{{kaudio}}}]] fehlt}}

| }} [[Media:{{{kaudio}}}|{{{k}}}]]^{?/[[:Datei:{{{kaudio}}}|ⓘ]]}

    | <phonos file="{{{kaudio}}}">{{{k}}}</phonos>^/?

}}

   | {{{k}}}
   }}

|{{#if:

 | {{#ifeq: 1 | 0
    | {{#if: {{{kaudio}}}

| {{#ifexist: Media:{{{kaudio}}}

   | Vorlage:CodexIcon{{#ifeq: 0 | 1 | ^{Vorlage:CodexIcon}}}
   | !?! [[:Datei:{{{kaudio}}}]] fehlt}}

| }} [[Media:{{{kaudio}}}|anhören (kantonesisch)]]^{?/[[:Datei:{{{kaudio}}}|ⓘ]]}

    | <phonos file="{{{kaudio}}}">anhören (kantonesisch)</phonos>^/?

}} }}}}{{#if:

 | , IPA (kantonesisch) <templatestyles src="IPA/styles.css" />{{#if:|[}}[{{{kipa}}}]{{#if:
    | ] <phonos file="{{{Tondatei}}}"></phonos>
  }}{{#invoke:TemplatePar|check

|all= 1= |opt= 2= Tondatei= |template=Vorlage:IPA |errNS= 0 |cat=Wikipedia:Vorlagenfehler/Vorlage:IPA |format=@@@ }} }}{{#if:

 | , englisch {{#invoke:Vorlage:lang|flat}}

}}{{#if:

 | , {{#ifeq: Chinesischer Restsatz | Taiwanische Sprache | Pe̍h-ōe-jī |Pe̍h-ōe-jī}} {{{poj}}}

}}{{#if: Mathematische Abhandlung in neun Kapiteln

 | – „Mathematische Abhandlung in neun Kapiteln“

}}) wiederveröffentlicht. Der Satz trifft eine Aussage über simultane Kongruenzen für den Fall, dass die Moduln teilerfremd sind. Sie lautet:

Sind <math>m_1, \ldots, m_n</math> paarweise teilerfremde natürliche Zahlen, dann existiert für jedes Tupel ganzer Zahlen <math>a_1, \ldots, a_n</math> eine ganze Zahl <math>x</math>, die die folgende simultane Kongruenz erfüllt:

<math>x \equiv a_i \mod m_i</math> für <math>i = 1, \ldots, n</math>

Alle Lösungen dieser Kongruenz sind kongruent modulo <math>M := m_1 m_2 m_3 \ldots m_n</math>.

Das Produkt <math>M</math> stimmt hier wegen der Teilerfremdheit mit dem <math>\operatorname{kgV}</math> überein.

Finden einer Lösung

Eine Lösung <math>x</math> kann wie folgt ermittelt werden: Für jedes <math>i</math> sind die Zahlen <math>m_i</math> und <math>M_i := M / m_i</math> teilerfremd, also kann man z. B. mit dem erweiterten euklidischen Algorithmus zwei ganze Zahlen <math>r_i</math> und <math>s_i</math> finden, so dass:

<math>r_i \cdot m_i + s_i \cdot M_i = 1</math>.

Setze <math>e_i := s_i \cdot M_i</math>, dann gilt:

<math>

\begin{align} e_i &\equiv 1 \pmod{m_i} \\ e_i &\equiv 0 \pmod{m_j}, \ j \neq i \end{align} </math>.

Die Zahl

ist dann eine Lösung der simultanen Kongruenz.

Beispiel

Gesucht sei eine ganze Zahl <math>x</math> mit der Eigenschaft

<math>

\begin{matrix} x & \equiv & 2 & \pmod 3 \\ x & \equiv & 3 & \pmod 4 \\ x & \equiv & 2 & \pmod 5 \\ \end{matrix} </math>

Hier ist <math>M = 3 \cdot 4 \cdot 5 = 60, \ M_1 = M/3 = 20, \ M_2 = M/4 = 15, \ M_3 = M/5 = 12</math>. Mit Hilfe des erweiterten euklidischen Algorithmus berechnet man

Eine Lösung ist dann <math>x = 2 \cdot (-20) + 3 \cdot (-15) + 2 \cdot (-24) = -133</math>. Wegen <math>-133 \equiv 47 \mod 60</math> sind alle anderen Lösungen also kongruent zu 47 modulo 60.

Allgemeiner Fall

Auch im Fall, dass die Moduln nicht teilerfremd sind, existiert manchmal eine Lösung. Die genaue Bedingung<ref>Einen Beweis dafür, dass diese Bedingung hinreichend ist, findet man bei A. Bogomolny: Chinese Remainder Theorem, Theorem 2 auf Interactive Mathematics Miscellany and Puzzles (englisch); die Notwendigkeit ist leicht zu sehen.</ref> lautet: Eine Lösung der simultanen Kongruenz existiert genau dann, wenn für alle <math>i \neq j</math> gilt:

<math>a_i \equiv a_j \mod{} \operatorname{ggT}(m_i, m_j)</math>,

wobei <math>\operatorname{ggT}(m_i, m_j)</math> für den größten gemeinsamen Teiler von <math>m_i</math> und <math>m_j</math> steht. Alle Lösungen sind dann kongruent modulo dem <math>\operatorname{kgV}</math> der <math>m_i</math>.

Eine simultane Kongruenz lässt sich im Falle der Existenz einer Lösung z. B. durch sukzessive Substitution lösen, auch wenn die Moduln nicht teilerfremd sind.

Beispiel

Ein klassisches Rätsel besteht darin, die kleinste natürliche Zahl zu finden, die bei Division durch 2, 3, 4, 5 und 6 jeweils den Rest 1 lässt, und durch 7 teilbar ist. Gesucht ist also die kleinste positive Lösung <math>x</math> der simultanen Kongruenz

<math>

\begin{matrix} x & \equiv & 1 & \mod 2 \\ x & \equiv & 1 & \mod 3 \\ x & \equiv & 1 & \mod 4 \\ x & \equiv & 1 & \mod 5 \\ x & \equiv & 1 & \mod 6 \\ x & \equiv & 0 & \mod 7 \\ \end{matrix} </math>

Da die Moduln nicht teilerfremd sind, kann man nicht direkt den chinesischen Restsatz (mit Lösungsverfahren) anwenden. Man kann aber die ersten fünf Bedingungen zusammenfassen zu <math>x \equiv 1 \mod \operatorname{kgV}(2, 3, 4, 5, 6)</math>, d. h. zu finden ist eine Lösung von

<math>

\begin{matrix} x & \equiv & 1 & \mod 60 \\ x & \equiv & 0 & \mod 7 \\ \end{matrix} </math>

Dieses Kongruenzsystem ist nun mit dem chinesischen Restsatz lösbar. Die Lösungen sind kongruent zu 301 modulo 420.

Direktes Lösen von simultanen Kongruenzen ganzer Zahlen

Gegeben sind die beiden simultanen Kongruenzen:

<math>

\begin{matrix} x & \equiv & a & \pmod{n} \\ x & \equiv & b & \pmod{m} \\ \end{matrix} </math> Wenn diese lösbar sind, das heißt <math>a \equiv b \pmod d</math>, so sind sie äquivalent mit der einfachen Kongruenz:

<math>

\begin{matrix} x & \equiv & a - yn \frac{a-b}{d} & \pmod{ \frac{nm}{d}} \\ \end{matrix} </math> mit

<math>d = \operatorname{ggT}(n,m) = yn + zm</math>.

Dieses funktioniert auch mit nicht teilerfremden Zahlen n und m und stellt somit eine deutliche Erleichterung bei dem Lösen von simultanen Kongruenzen dar.

Ein System aus Kongruenzen lässt sich durch wiederholtes Anwenden dieser Vereinfachung lösen.

Aussage für Hauptidealringe

Sei <math>R</math> ein Hauptidealring, dann lautet der chinesische Restsatz für <math>R</math> wie folgt:

Sind <math>m_1, \ldots, m_n</math> paarweise teilerfremd und <math>m</math> ihr Produkt, dann ist der Faktorring <math>R/mR</math> isomorph zum Produktring <math>R/m_1 R \times \cdots \times R/m_n R</math> durch den Isomorphismus

<math>

\begin{matrix} f : & R/mR & \to & R/m_1R \times \cdots \times R/m_nR \\

 & x + mR & \mapsto & (x + m_1R, \ldots, x + m_nR)

\end{matrix} </math>

Aussage für allgemeine Ringe

Eine der allgemeinsten Formen des chinesischen Restsatzes ist eine Formulierung für einen beliebigen Ring <math>R</math> (mit Einselement).

Sind <math>I_1, \ldots, I_n</math> (beidseitige) Ideale, so dass <math>I_i + I_j = R</math> für <math>i \neq j</math> (man nennt die Ideale dann teilerfremd oder coprim), und sei <math>I</math> der Durchschnitt der Ideale, dann ist der Faktorring <math>R/I</math> isomorph zum Produktring <math>R/I_1 \times \cdots \times R/I_n</math> durch den Isomorphismus

<math>

\begin{matrix} f : & R/I & \to & R/I_1 \times \cdots \times R/I_n \\

 & x + I & \mapsto & (x + I_1, \ldots, x + I_n).

\end{matrix} </math> (<math>I</math> ist auch gleich dem Produkt der <math>I_j</math>, falls <math>R</math> ein kommutativer Ring ist.)

Diese Aussage lässt sich wie folgt beweisen: <math>f</math> ist ein Ringhomomorphismus und <math>f</math> ist genau dann ein Isomorphismus, wenn <math>f\otimes_R \operatorname{id}_{R_\mathfrak{p}}</math>ein Isomorphismus ist für alle Primideale <math>\mathfrak p\subseteq R</math>. Da Lokalisierung mit Durchschnitt und Quotientenbildung verträglich ist, kann man ohne Einschränkung annehmen, dass <math>R</math> ein lokaler Ring ist mit einzigem maximalen Ideal <math>\mathfrak{m}</math>. Wenn <math>I_i\subseteq\mathfrak{m}</math> und <math>I_j\subseteq\mathfrak{m}</math>, dann ist auch <math>I_i+I_j\subseteq m\subsetneq R</math>. Da jedes Ideal ungleich <math>R</math> in dem maximalen Ideal <math>\mathfrak{m}</math> enthalten sein muss, ist <math>I_i\neq R</math> für höchstens ein <math>i</math>. Wenn alle <math>I_i</math> gleich dem ganzen Ring <math>R</math> sind, dann ist die Aussage wahr, denn dann ist <math>f\colon \{0\}\to \prod_{i=1}^n\{0\}\cong\{0\}</math> ein Isomorphismus. Sei also ohne Einschränkung <math>I_1</math> das einzige Ideal <math>I_i</math>, sodass <math>I_i\neq R</math>.

Es ist <math>I_1\cdots I_r=I_1\cdot R\cdots R=I_1=I</math> und außerdem

<math>R/I=R/I_1\cong R/I_1\times\{0\}\times\dots\times\{0\}=R/I_i\times R/R\times\dots\times R/R\cong\prod_{i=1}^nR/I_i</math>

Weblinks

[[b:{{#if:|{{{lang}}}:}}{{#if:Beweisarchiv: Algebra: Ringe: Chinesischer Restsatz|Beweisarchiv: Algebra: Ringe: Chinesischer Restsatz|Chinesischer Restsatz}}|Wikibooks: {{#if:Beweis des Satzes im Beweisarchiv|Beweis des Satzes im Beweisarchiv|{{#if:Beweisarchiv: Algebra: Ringe: Chinesischer Restsatz|Beweisarchiv: Algebra: Ringe: Chinesischer Restsatz|Chinesischer Restsatz}}}}]]{{#switch: 1

|1|= – Lern- und Lehrmaterialien |0|-= |X|x={{#switch: 0

      |0|4|10|12|14|100=}}

|#default= – {{{suffix}}}

}}{{#if: | ({{#invoke:Multilingual|format|{{{lang}}}|slang=!|shift=m}}) }}

{{#invoke:TemplatePar|check

  |opt= 1= 2= lang= suffix=
  |template=Vorlage:Wikibooks
  |cat=Wikipedia:Vorlagenfehler/Schwesterprojekt
  }}

Programm zur Berechnung simultaner Kongruenzen
Chinese Remainder Theorem in der Encyclopaedia of Mathematics
{{#if: | {{{author}}} | Eric W. Weisstein }}: Chinese Remainder Theorem. In: MathWorld (englisch). {{#if: ChineseRemainderTheorem | {{#ifeq: {{#property:P2812}} | ChineseRemainderTheorem | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}
Christian Spannagel: Chinesischer Restsatz. Vorlesungsreihe, 2012.
Chinese Remainder Theorem. Planetmath.org (englisch).

Einzelnachweise

{{#ifeq: s | p | | {{#if: 4470755-1sh/97/2778 | |

}} }}Vorlage:Hinweisbaustein{{#ifeq: s | p | | {{#if: 4470755-1sh/97/2778 | |

}} }}{{#ifeq:||{{#if: | [[Kategorie:Wikipedia:GND fehlt {{#invoke:Str|left|{{{GNDCheck}}}|7}}]] }}{{#if: | {{#if: | | }} }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#ifeq: s | p | {{#if: 4470755-1 | | {{#if: {{#statements:P227}} | | }} }} }}{{#ifeq: s | p | {{#if: 4470755-1 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P227}} | | }} }} }} }}{{#ifeq: s | p | {{#if: sh/97/2778 | | {{#if: {{#statements:P244}} | | }} }} }}{{#ifeq: s | p | {{#if: sh/97/2778 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P244}} | | }} }} }} }}{{#ifeq: s | p | {{#if: | | {{#if: {{#statements:P214}} | | }} }} }}{{#ifeq: s | p | {{#if: | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P214}} | | }} }} }} }}Vorlage:Wikidata-Registrierung