https://vik.wiki/index.php?action=history&feed=atom&title=17._t%C3%A9tel 2026-05-17T10:47:19Z Az oldal laptörténete a wikiben MediaWiki 1.43.8 https://vik.wiki/index.php?title=17._t%C3%A9tel&diff=138215&oldid=prev 2012-10-21T20:15:03Z

<p>Új oldal, tartalma: „{{GlobalTemplate|Infoalap|SzamElmTetelA17}} <a href="/index.php?title=SzamelmSzig&amp;action=edit&amp;redlink=1" class="new" title="SzamelmSzig (a lap nem létezik)">SzamelmSzig</a> &gt; <a href="/DaniVeloxKidolgozas" title="DaniVeloxKidolgozas">DaniVeloxKidolgozas</a> &gt; *Teljes és redukált maradékrendszer, φ-függvény definíciója. …”</p> <p><b>Új lap</b></p><div>{{GlobalTemplate|Infoalap|SzamElmTetelA17}}<br /> <br /> [[SzamelmSzig]] &amp;gt; [[DaniVeloxKidolgozas]] &amp;gt;<br /> *Teljes és redukált maradékrendszer, &amp;#966;-függvény definíciója. Euler-Fermat-tétel &#039;&#039;&#039;, kis Fermat-tétel. Euklideszi algoritmus.&#039;&#039;&#039;<br /> <br /> Ha a mod m maradékosztályok mindegyikéből kiválasztunk egy tetszőleges elemet, a keletkező számhalmazt mod m _teljes maradékrendszer_nek nevezzük.<br /> A mod m maradékosztályok közül azokból, melyek minden eleme relatív prím m-hez kiveszünk egyet-egyet, a keletkező számhalmazt mod m _redukált maradékrendszer_ének nevezzük.<br /> _&amp;phi;(m)_: az m-nél kisebb, m-hez relatív prímek száma<br /> <br /> *Tétel*: _Euler-Fermat_: Ha m&gt;1 tetszőleges egész szám és a tetszőleges olyan szám, melyre (a,m)=1, akkor a&lt;sup&gt;&amp;#966;(m)&lt;/sup&gt;&amp;#8801;1 (mod m).<br /> <br /> *Tétel*: _&amp;#8222;kis&amp;#8221; Fermat_: Tetszőleges p prímszámra és tetszőleges a egész számra a&lt;sup&gt;p&lt;/sup&gt;&amp;equiv;a (mod p)<br /> <br /> *Bizonyítás*:&lt;br/&gt;<br /> 1. p|a =&gt; 0&amp;equiv;a&lt;sup&gt;p&lt;/sup&gt;&amp;equiv;a&amp;equiv;0 (mod p)&lt;br/&gt;<br /> 2. nem p|a =&gt; (p,a)=1 =&gt;{Euler Fermat}=&gt; a&lt;sup&gt;&amp;#966;(p)&lt;/sup&gt;&amp;#8801;1 (mod p) &lt;br/&gt; &amp;phi;(p)=p-1, így a&lt;sup&gt;p-1&lt;/sup&gt;&amp;#8801;1 (mod p), azaz a&lt;sup&gt;p&lt;/sup&gt;&amp;equiv;a (mod p)<br /> <br /> _Euklideszi algoritmus_: a,b számok legnagyobb közös osztójának kiszámításához.&lt;br/&gt;<br /> a = h&lt;sub&gt;1&lt;/sub&gt;b+m&lt;sub&gt;1&lt;/sub&gt; (0&amp;#8804;m&lt;sub&gt;1&lt;/sub&gt;&lt;b)&lt;br/&gt;<br /> b = h&lt;sub&gt;2&lt;/sub&gt;m&lt;sub&gt;1&lt;/sub&gt;+m&lt;sub&gt;2&lt;/sub&gt; (0&amp;#8804;m&lt;sub&gt;2&lt;/sub&gt;&lt;m&lt;sub&gt;1&lt;/sub&gt;)&lt;br/&gt;<br /> m&lt;sub&gt;1&lt;/sub&gt; = h&lt;sub&gt;3&lt;/sub&gt;m&lt;sub&gt;2&lt;/sub&gt;+m&lt;sub&gt;3&lt;/sub&gt;(0&amp;#8804;m&lt;sub&gt;3&lt;/sub&gt;&lt;m&lt;sub&gt;2&lt;/sub&gt;)&lt;br/&gt;<br /> és így tovább.&lt;br/&gt;<br /> Az eljárás akkor ér véget, ha nincs az osztásnak maradéka, vagyis m&lt;sub&gt;n-2&lt;/sub&gt;=h&lt;sub&gt;n&lt;/sub&gt;m&lt;sub&gt;n-1&lt;/sub&gt;. m&lt;sub&gt;n-3&lt;/sub&gt;=h&lt;sub&gt;n-1&lt;/sub&gt;m&lt;sub&gt;n-2&lt;/sub&gt;+ m&lt;sub&gt;n-1&lt;/sub&gt;=(h&lt;sub&gt;n-1&lt;/sub&gt;h&lt;sub&gt;n&lt;/sub&gt;+1)m&lt;sub&gt;n-1&lt;/sub&gt;,&amp;#8230; a és b is m&lt;sub&gt;n-1&lt;/sub&gt; többszöröse lesz,&amp;#8594;m&lt;sub&gt;n-1&lt;/sub&gt; közös osztója a-nak és b-nek. Megfordítva, a és b tetszőleges közös osztója m&lt;sub&gt;1&lt;/sub&gt;-nek is osztója&amp;#8230;m&lt;sub&gt;n-1&lt;/sub&gt;-nek is. Tehát m&lt;sub&gt;n-1&lt;/sub&gt;= (a,b). Másképp: (a,b)=(b,m&lt;sub&gt;1&lt;/sub&gt;)=(m&lt;sub&gt;1&lt;/sub&gt;,m&lt;sub&gt;2&lt;/sub&gt;)=&amp;#8230;=(m&lt;sub&gt;n-2&lt;/sub&gt;,m&lt;sub&gt;n-1&lt;/sub&gt;)=m&lt;sub&gt;n-1&lt;/sub&gt;&amp;#8594;a és b közös osztóinak halmaza megegyezik legnagyobb közös osztójuk osztóinak halmazával.<br /> <br /> <br /> -- [[SzaMa|SzaMa]] - 2005.09.17.<br /> <br /> <br /> [[Category:Infoalap]]</div>

Unknown user