|
|
|
|
Quelle chap15.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/doc/ref/chap15.html |
 |
<?xml version= "1.0" encoding= "UTF-8"?>
<! DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
< html xmlns= "http://www.w3.org/1999/xhtml" xml:lang= "en">
< head>
< title>GAP (ref) - Chapter 15: Number Theory</ title>
< meta http-equiv= "content-type" content= "text/html; charset=UTF-8" />
< meta name= "generator" content= "GAPDoc2HTML" />
< link rel= "stylesheet" type= "text/css" href= "manual.css" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap15" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span><a href= "chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chap19.html">19</a> <a href="chap20.html">20</a> <a href="chap21.html">21</a> <a href="chap22.html">22</a> <a href="chap23.html">23</a> <a href="chap24.html">24</a> <a href="chap25.html">25</a> <a href="chap26.html">26</a> <a href="chap27.html">27</a> <a href="chap28.html">28</a> <a href="chap29.html">29</a> <a href="chap30.html">30</a> <a href="chap31.html">31</a> <a href="chap32.html">32</a> <a href="chap33.html">33</a> <a href="chap34.html">34</a> <a href="chap35.html">35</a> <a href="chap36.html">36</a> <a href="chap37.html">37</a> <a href="chap38.html">38</a> <a href="chap39.html">39</a> <a href="chap40.html">40</a> <a href="chap41.html">41</a> <a href="chap42.html">42</a> <a href="chap43.html">43</a> <a href="chap44.html">44</a> <a href="chap45.html">45</a> <a href="chap46.html">46</a> <a href="chap47.html">47</a> <a href="chap48.html">48</a> <a href="chap49.html">49</a> <a href="chap50.html">50</a> <a href="chap51.html">51</a> <a href="chap52.html">52</a> <a href="chap53.html">53</a> <a href="chap54.html">54</a> <a href="chap55.html">55</a> <a href="chap56.html">56</a> <a href="chap57.html">57</a> <a href="chap58.html">58</a> <a href="chap59.html">59</a> <a href="chap60.html">60</a> <a href="chap61.html">61</a> <a href="chap62.html">62</a> <a href="chap63.html">63</a> <a href="chap64.html">64</a> <a href="chap65.html">65</a> <a href="chap66.html">66</a> <a href="chap67.html">67</a> <a href="chap68.html">68</a> <a href="chap69.html">69</a> <a href="chap70.html">70</a> <a href="chap71.html">71</a> <a href="chap72.html">72</a> <a href="chap73.html">73</a> <a href="chap74.html">74</a> <a href="chap75.html">75</a> <a href="chap76.html">76</a> <a href="chap77.html">77</a> <a href="chap78.html">78</a> <a href="chap79.html">79</a> <a href="chap80.html">80</a> <a href="chap81.html">81</a> <a href="chap82.html">82</a> <a href="chap83.html">83</a> <a href="chap84.html">84</a> <a href="chap85.html">85</a> <a href="chap86.html">86</a> <a href="chap87.html">87</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap14.html">[Previous Chapter]</a> <a href="chap16.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap15_mj.html">[MathJax on]</a></p>
<p><a id="X7FB995737B7ED8A2" name="X7FB995737B7ED8A2"></a></p>
<div class="ChapSects"><a href="chap15.html#X7FB995737B7ED8A2">15 <span class="Heading">Number Theory</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7845C1F97A1742C7">15.1 <span class="Heading">InfoNumtheor (Info Class)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X796F0DFE7D5D211C">15.1-1 InfoNumtheor</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X823386567DAC22E6">15.2 <span class="Heading">Prime Residues</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7FA3F5347B7004BA">15.2-1 PrimeResidues</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X85A0C67982D9057A">15.2-2 Phi</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X85296F3087611B03">15.2-3 Lambda</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7D191CF67E5018BE">15.2-4 GeneratorsPrimeResidues</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X83103A5385821BAE">15.3 <span class="Heading">Primitive Roots and Discrete Logarithms</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X82373F3D8277EE9E">15.3-1 OrderMod</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X81AD9C7779A7BA89">15.3-2 LogMod</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X84A138947E8C49A8">15.3-3 DLog</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X82440BB9812FF148">15.3-4 PrimitiveRootMod</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X790466C07BD90E20">15.3-5 IsPrimitiveRootMod</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7F9069D77AC48054">15.4 <span class="Heading">Roots Modulo Integers</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X83449DBC80495971">15.4-1 Jacobi</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X81464ABF7F10E544">15.4-2 Legendre</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X83E3ED577B7A04ED">15.4-3 RootMod</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X84D3F03B862841F8">15.4-4 RootsMod</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X81F856E682A8ECBA">15.4-5 RootsUnityMod</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7B3A5A0378A32F83">15.5 <span class="Heading">Multiplicative Arithmetic Functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X823707DF821E79A0">15.5-1 Sigma</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X798C62847EE0372E">15.5-2 Tau</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X79C1DA36827C2959">15.5-3 MoebiusMu</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7B2E061C835159B9">15.6 <span class="Heading">Continued Fractions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X874C161B83416092">15.6-1 ContinuedFractionExpansionOfRoot</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X8059667580A039A6">15.6-2 ContinuedFractionApproximationOfRoot</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7C5563A37D566DA5">15.7 <span class="Heading">Miscellaneous</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X8243EAA586D78ED4">15.7-1 PValuation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X85E1EFC484F648A4">15.7-2 TwoSquares</a></span>
</div></div>
</div>
<h3>15 <span class="Heading">Number Theory</span></h3>
<p><strong class="pkg">GAP</strong> provides a couple of elementary number theoretic functions. Most of these deal with the group of integers coprime to <span class="SimpleMath">m</span>, called the <em>prime residue group</em>. The order of this group is <span class="SimpleMath">ϕ(m)</span> (see <code class="func">Phi</code> (<a href="chap15.html#X85A0C67982D9057A"><span class="RefLink">15.2-2</span></a>)), and <span class="SimpleMath">λ(m)</span> (see <code class="func">Lambda</code> (<a href="chap15.html#X85296F3087611B03"><span class="RefLink">15.2-3</span></a>)) is its exponent. This group is cyclic if and only if <span class="SimpleMath">m</span> is 2, 4, an odd prime power <span class="SimpleMath">p^n</span>, or twice an odd prime power <span class="SimpleMath">2 p^n</span>. In this case the generators of the group, i.e., elements of order <span class="SimpleMath">ϕ(m)</span>, are called <em>primitive roots</em> (see <code class="func">PrimitiveRootMod</code> (<a href="chap15.html#X82440BB9812FF148"><span class="RefLink">15.3-4</span></a>)).</p>
<p>Note that neither the arguments nor the return values of the functions listed below are groups or group elements in the sense of <strong class="pkg">GAP</strong>. The arguments are simply integers.</p>
<p><a id="X7845C1F97A1742C7" name="X7845C1F97A1742C7"></a></p>
<h4>15.1 <span class="Heading">InfoNumtheor (Info Class)</span></h4>
<p><a id="X796F0DFE7D5D211C" name="X796F0DFE7D5D211C"></a></p>
<h5>15.1-1 InfoNumtheor</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InfoNumtheor</code></td><td class="tdright">( info class )</td></tr></table></div>
<p><code class="func">InfoNumtheor</code> is the info class (see <a href="chap7.html#X7A9C902479CB6F7C"><span class="RefLink">7.4</span></a>) for the functions in the number theory chapter.</p>
<p><a id="X823386567DAC22E6" name="X823386567DAC22E6"></a></p>
<h4>15.2 <span class="Heading">Prime Residues</span></h4>
<p><a id="X7FA3F5347B7004BA" name="X7FA3F5347B7004BA"></a></p>
<h5>15.2-1 PrimeResidues</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrimeResidues</code>( <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">PrimeResidues</code> returns the set of integers from the range <code class="code">[ 0 .. Abs( <var class="Arg">m</var> )-1 ]</code> that are coprime to the integer <var class="Arg">m</var>.</p>
<p><code class="code">Abs(<var class="Arg">m</var>)</code> must be less than <span class="SimpleMath">2^28</span>, otherwise the set would probably be too large anyhow.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrimeResidues( 0 ); PrimeResidues( 1 ); PrimeResidues( 20 );</span>
[ ]
[ 0 ]
[ 1, 3, 7, 9, 11, 13, 17, 19 ]
</pre></div>
<p><a id="X85A0C67982D9057A" name="X85A0C67982D9057A"></a></p>
<h5>15.2-2 Phi</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Phi</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">Phi</code> returns the number <span class="SimpleMath">ϕ(<var class="Arg">m</var>)</span> of positive integers less than the positive integer <var class="Arg">m</var> that are coprime to <var class="Arg">m</var>.</p>
<p>Suppose that <span class="SimpleMath">m = p_1^{e_1} p_2^{e_2} ⋯ p_k^{e_k}</span>. Then <span class="SimpleMath">ϕ(m)</span> is <span class="SimpleMath">p_1^{e_1-1} (p_1-1) p_2^{e_2-1} (p_2-1) ⋯ p_k^{e_k-1} (p_k-1)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Phi( 12 );</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">Phi( 2^13-1 ); # this proves that 2^(13)-1 is a prime</span>
8190
<span class="GAPprompt">gap></span> <span class="GAPinput">Phi( 2^15-1 );</span>
27000
</pre></div>
<p><a id="X85296F3087611B03" name="X85296F3087611B03"></a></p>
<h5>15.2-3 Lambda</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Lambda</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">Lambda</code> returns the exponent <span class="SimpleMath">λ(<var class="Arg">m</var>)</span> of the group of prime residues modulo the integer <var class="Arg">m</var>.</p>
<p><span class="SimpleMath">λ(<var class="Arg">m</var>)</span> is the smallest positive integer <span class="SimpleMath">l</span> such that for every <span class="SimpleMath">a</span> relatively prime to <var class="Arg">m</var> we have <span class="SimpleMath">a^l ≡ 1 mod <var class="Arg">m</var></span>. Fermat's theorem asserts a^{ϕ(m)} ≡ 1 mod m; thus λ(m) divides ϕ(m) (see Phi (15.2-2)).
<p>Carmichael's theorem states that λ can be computed as follows: λ(2) = 1, λ(4) = 2 and λ(2^e) = 2^{e-2} if 3 ≤ e, λ(p^e) = (p-1) p^{e-1} (i.e. ϕ(m)) if p is an odd prime and λ(m*n) =Lcm( λ(m), λ(n) ) if m, n are coprime.
<p>Composites for which <span class="SimpleMath">λ(m)</span> divides <span class="SimpleMath">m - 1</span> are called Carmichaels. If <span class="SimpleMath">6k+1</span>, <span class="SimpleMath">12k+1</span> and <span class="SimpleMath">18k+1</span> are primes their product is such a number. There are only 1547 Carmichaels below <span class="SimpleMath">10^10</span> but 455052511 primes.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lambda( 10 );</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">Lambda( 30 );</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">Lambda( 561 ); # 561 is the smallest Carmichael number</span>
80
</pre></div>
<p><a id="X7D191CF67E5018BE" name="X7D191CF67E5018BE"></a></p>
<h5>15.2-4 GeneratorsPrimeResidues</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsPrimeResidues</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">n</var> be a positive integer. <code class="func">GeneratorsPrimeResidues</code> returns a description of generators of the group of prime residues modulo <var class="Arg">n</var>. The return value is a record with components</p>
<dl>
<dt><strong class="Mark"><code class="code">primes</code>: </strong></dt>
<dd><p>a list of the prime factors of <var class="Arg">n</var>,</p>
</dd>
<dt><strong class="Mark"><code class="code">exponents</code>: </strong></dt>
<dd><p>a list of the exponents of these primes in the factorization of <var class="Arg">n</var>, and</p>
</dd>
<dt><strong class="Mark"><code class="code">generators</code>: </strong></dt>
<dd><p>a list describing generators of the group of prime residues; for the prime factor <span class="SimpleMath">2</span>, either a primitive root or a list of two generators is stored, for each other prime factor of <var class="Arg">n</var>, a primitive root is stored.</p>
</dd>
</dl>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsPrimeResidues( 1 );</span>
rec( exponents := [ ], generators := [ ], primes := [ ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsPrimeResidues( 4*3 );</span>
rec( exponents := [ 2, 1 ], generators := [ 7, 5 ],
primes := [ 2, 3 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsPrimeResidues( 8*9*5 );</span>
rec( exponents := [ 3, 2, 1 ],
generators := [ [ 271, 181 ], 281, 217 ], primes := [ 2, 3, 5 ] )
</pre></div>
<p><a id="X83103A5385821BAE" name="X83103A5385821BAE"></a></p>
<h4>15.3 <span class="Heading">Primitive Roots and Discrete Logarithms</span></h4>
<p><a id="X82373F3D8277EE9E" name="X82373F3D8277EE9E"></a></p>
<h5>15.3-1 OrderMod</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrderMod</code>( <var class="Arg">n</var>, <var class="Arg">m</var>[, <var class="Arg">bound</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">OrderMod</code> returns the multiplicative order of the integer <var class="Arg">n</var> modulo the positive integer <var class="Arg">m</var>. If <var class="Arg">n</var> and <var class="Arg">m</var> are not coprime the order of <var class="Arg">n</var> is not defined and <code class="func">OrderMod</code> will return <code class="code">0</code>.</p>
<p>If <var class="Arg">n</var> and <var class="Arg">m</var> are relatively prime the multiplicative order of <var class="Arg">n</var> modulo <var class="Arg">m</var> is the smallest positive integer <span class="SimpleMath">i</span> such that <span class="SimpleMath"><var class="Arg">n</var>^i ≡ 1 mod <var class="Arg">m</var></span>. If the group of prime residues modulo <var class="Arg">m</var> is cyclic then each element of maximal order is called a primitive root modulo <var class="Arg">m</var> (see <code class="func">IsPrimitiveRootMod</code> (<a href="chap15.html#X790466C07BD90E20"><span class="RefLink">15.3-5</span></a>)).</p>
<p>If no a priori known multiple <var class="Arg">bound</var> of the desired order is given, <code class="func">OrderMod</code> usually spends most of its time factoring <var class="Arg">m</var> for computing <span class="SimpleMath">λ(<var class="Arg">m</var>)</span> (see <code class="func">Lambda</code> (<a href="chap15.html#X85296F3087611B03"><span class="RefLink">15.2-3</span></a>)) as the default for <var class="Arg">bound</var>, and then factoring <var class="Arg">bound</var> (see <code class="func">FactorsInt</code> (<a href="chap14.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>)).</p>
<p>If an incorrect <var class="Arg">bound</var> is given then the result will be wrong.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">OrderMod( 2, 7 );</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">OrderMod( 3, 7 ); # 3 is a primitive root modulo 7</span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">m:= (5^166-1) / 167;; # about 10^113</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">OrderMod( 5, m, 166 ); # needs minutes without third argument</span>
166
</pre></div>
<p><a id="X81AD9C7779A7BA89" name="X81AD9C7779A7BA89"></a></p>
<h5>15.3-2 LogMod</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LogMod</code>( <var class="Arg">n</var>, <var class="Arg">r</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LogModShanks</code>( <var class="Arg">n</var>, <var class="Arg">r</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>computes the discrete <var class="Arg">r</var>-logarithm of the integer <var class="Arg">n</var> modulo the integer <var class="Arg">m</var>. It returns a number <var class="Arg">l</var> such that <span class="SimpleMath"><var class="Arg">r</var>^<var class="Arg">l</var> ≡ <var class="Arg">n</var> mod <var class="Arg">m</var></span> if such a number exists. Otherwise <code class="keyw">fail</code> is returned.</p>
<p><code class="func">LogModShanks</code> uses the Baby Step - Giant Step Method of Shanks (see for example <a href="chapBib.html#biBCoh93">[Coh93, section 5.4.1]</a>) and in general requires more memory than a call to <code class="func">LogMod</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= LogMod( 2, 5, 7 ); 5^l mod 7 = 2;</span>
4
true
<span class="GAPprompt">gap></span> <span class="GAPinput">LogMod( 1, 3, 3 ); LogMod( 2, 3, 3 );</span>
0
fail
</pre></div>
<p><a id="X84A138947E8C49A8" name="X84A138947E8C49A8"></a></p>
<h5>15.3-3 DLog</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DLog</code>( <var class="Arg">base</var>, <var class="Arg">x</var>[, <var class="Arg">m</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an integer</p>
<p>The argument <var class="Arg">base</var> must be a multiplicative element and <var class="Arg">x</var> must lie in the cyclic group generated by <var class="Arg">base</var>. The third argument <var class="Arg">m</var> must be the order of <var class="Arg">base</var> or its factorization. If <var class="Arg">m</var> is not given, it is computed first. This function returns the discrete logarithm, that is an integer <span class="SimpleMath">e</span> such that <var class="Arg">base</var><span class="SimpleMath">^e =</span> <var class="Arg">x</var>.</p>
<p>If <var class="Arg">m</var> is prime then Shanks' algorithm is used (which needs O(sqrtm) space and time). Otherwise let m = r l and e = a + b r with 0 ≤ a < r. Then a = DLog(base^l, x^l, r) and b = DLog(base^r, x/base^a, l).
<p>This function is used for a method of <code class="func">LogFFE</code> (<a href="chap59.html#X7B049A3478B369E4"><span class="RefLink">59.2-2</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">q:= 67^12;</span>
8182718904632857144561
<span class="GAPprompt">gap></span> <span class="GAPinput">z:= Z(q);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DLog(z, z+1);</span>
2874413785388345993274
<span class="GAPprompt">gap></span> <span class="GAPinput">DLog(z, z^2+1);</span>
1667375214152688471247
<span class="GAPprompt">gap></span> <span class="GAPinput">DLog(z, Z(67));</span>
123980589464134199160
</pre></div>
<p><a id="X82440BB9812FF148" name="X82440BB9812FF148"></a></p>
<h5>15.3-4 PrimitiveRootMod</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrimitiveRootMod</code>( <var class="Arg">m</var>[, <var class="Arg">start</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">PrimitiveRootMod</code> returns the smallest primitive root modulo the positive integer <var class="Arg">m</var> and <code class="keyw">fail</code> if no such primitive root exists. If the optional second integer argument <var class="Arg">start</var> is given <code class="func">PrimitiveRootMod</code> returns the smallest primitive root that is strictly larger than <var class="Arg">start</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput"># largest primitive root for a prime less than 2000:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrimitiveRootMod( 409 );</span>
21
<span class="GAPprompt">gap></span> <span class="GAPinput">PrimitiveRootMod( 541, 2 );</span>
10
<span class="GAPprompt">gap></span> <span class="GAPinput"># 327 is the largest primitive root mod 337:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrimitiveRootMod( 337, 327 );</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput"># there exists no primitive root modulo 30:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrimitiveRootMod( 30 );</span>
fail
</pre></div>
<p><a id="X790466C07BD90E20" name="X790466C07BD90E20"></a></p>
<h5>15.3-5 IsPrimitiveRootMod</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPrimitiveRootMod</code>( <var class="Arg">r</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IsPrimitiveRootMod</code> returns <code class="keyw">true</code> if the integer <var class="Arg">r</var> is a primitive root modulo the positive integer <var class="Arg">m</var>, and <code class="keyw">false</code> otherwise. If <var class="Arg">r</var> is less than 0 or larger than <var class="Arg">m</var> it is replaced by its remainder.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimitiveRootMod( 2, 541 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimitiveRootMod( -539, 541 ); # same computation as above;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimitiveRootMod( 4, 541 );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAny( [1..29], r -> IsPrimitiveRootMod( r, 30 ) );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput"># there is no a primitive root modulo 30</span>
</pre></div>
<p><a id="X7F9069D77AC48054" name="X7F9069D77AC48054"></a></p>
<h4>15.4 <span class="Heading">Roots Modulo Integers</span></h4>
<p><a id="X83449DBC80495971" name="X83449DBC80495971"></a></p>
<h5>15.4-1 Jacobi</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Jacobi</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">Jacobi</code> returns the value of the <em>Kronecker-Jacobi symbol</em> <span class="SimpleMath">J(<var class="Arg">n</var>,<var class="Arg">m</var>)</span> of the integer <var class="Arg">n</var> modulo the integer <var class="Arg">m</var>. It is defined as follows:</p>
<p>If <span class="SimpleMath">n</span> and <span class="SimpleMath">m</span> are not coprime then <span class="SimpleMath">J(n,m) = 0</span>. Furthermore, <span class="SimpleMath">J(n,1) = 1</span> and <span class="SimpleMath">J(n,-1) = -1</span> if <span class="SimpleMath">m < 0</span> and <span class="SimpleMath">+1</span> otherwise. And for odd <span class="SimpleMath">n</span> it is <span class="SimpleMath">J(n,2) = (-1)^k</span> with <span class="SimpleMath">k = (n^2-1)/8</span>. For odd primes <span class="SimpleMath">m</span> which are coprime to <span class="SimpleMath">n</span> the Kronecker-Jacobi symbol has the same value as the Legendre symbol (see <code class="func">Legendre</code> (<a href="chap15.html#X81464ABF7F10E544"><span class="RefLink">15.4-2</span></a>)).</p>
<p>For the general case suppose that <span class="SimpleMath">m = p_1 ⋅ p_2 ⋯ p_k</span> is a product of <span class="SimpleMath">-1</span> and of primes, not necessarily distinct, and that <span class="SimpleMath">n</span> is coprime to <span class="SimpleMath">m</span>. Then <span class="SimpleMath">J(n,m) = J(n,p_1) ⋅ J(n,p_2) ⋯ J(n,p_k)</span>.</p>
<p>Note that the Kronecker-Jacobi symbol coincides with the Jacobi symbol that is defined for odd <span class="SimpleMath">m</span> in many number theory books. For odd primes <span class="SimpleMath">m</span> and <span class="SimpleMath">n</span> coprime to <span class="SimpleMath">m</span> it coincides with the Legendre symbol.</p>
<p><code class="func">Jacobi</code> is very efficient, even for large values of <var class="Arg">n</var> and <var class="Arg">m</var>, it is about as fast as the Euclidean algorithm (see <code class="func">Gcd</code> (<a href="chap56.html#X7DE207718456F98F"><span class="RefLink">56.7-1</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Jacobi( 11, 35 ); # 9^2 = 11 mod 35</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput"># this is -1, thus there is no r such that r^2 = 6 mod 35</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Jacobi( 6, 35 );</span>
-1
<span class="GAPprompt">gap></span> <span class="GAPinput"># this is 1 even though there is no r with r^2 = 3 mod 35</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Jacobi( 3, 35 );</span>
1
</pre></div>
<p><a id="X81464ABF7F10E544" name="X81464ABF7F10E544"></a></p>
<h5>15.4-2 Legendre</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Legendre</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">Legendre</code> returns the value of the <em>Legendre symbol</em> of the integer <var class="Arg">n</var> modulo the positive integer <var class="Arg">m</var>.</p>
<p>The value of the Legendre symbol <span class="SimpleMath">L(n/m)</span> is 1 if <span class="SimpleMath">n</span> is a <em>quadratic residue</em> modulo <span class="SimpleMath">m</span>, i.e., if there exists an integer <span class="SimpleMath">r</span> such that <span class="SimpleMath">r^2 ≡ n mod m</span> and <span class="SimpleMath">-1</span> otherwise.</p>
<p>If a root of <var class="Arg">n</var> exists it can be found by <code class="func">RootMod</code> (<a href="chap15.html#X83E3ED577B7A04ED"><span class="RefLink">15.4-3</span></a>).</p>
<p>While the value of the Legendre symbol usually is only defined for <var class="Arg">m</var> a prime, we have extended the definition to include composite moduli too. The Jacobi symbol (see <code class="func">Jacobi</code> (<a href="chap15.html#X83449DBC80495971"><span class="RefLink">15.4-1</span></a>)) is another generalization of the Legendre symbol for composite moduli that is much cheaper to compute, because it does not need the factorization of <var class="Arg">m</var> (see <code class="func">FactorsInt</code> (<a href="chap14.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>)).</p>
<p>A description of the Jacobi symbol, the Legendre symbol, and related topics can be found in <a href="chapBib.html#biBBaker84">[Bak84]</a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Legendre( 5, 11 ); # 4^2 = 5 mod 11</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput"># this is -1, thus there is no r such that r^2 = 6 mod 11</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Legendre( 6, 11 );</span>
-1
<span class="GAPprompt">gap></span> <span class="GAPinput"># this is -1, thus there is no r such that r^2 = 3 mod 35</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Legendre( 3, 35 );</span>
-1
</pre></div>
<p><a id="X83E3ED577B7A04ED" name="X83E3ED577B7A04ED"></a></p>
<h5>15.4-3 RootMod</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RootMod</code>( <var class="Arg">n</var>[, <var class="Arg">k</var>], <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">RootMod</code> computes a <var class="Arg">k</var>th root of the integer <var class="Arg">n</var> modulo the positive integer <var class="Arg">m</var>, i.e., a <span class="SimpleMath">r</span> such that <span class="SimpleMath">r^<var class="Arg">k</var> ≡ <var class="Arg">n</var> mod <var class="Arg">m</var></span>. If no such root exists <code class="func">RootMod</code> returns <code class="keyw">fail</code>. If only the arguments <var class="Arg">n</var> and <var class="Arg">m</var> are given, the default value for <var class="Arg">k</var> is <span class="SimpleMath">2</span>.</p>
<p>A square root of <var class="Arg">n</var> exists only if <code class="code">Legendre(<var class="Arg">n</var>,<var class="Arg">m</var>) = 1</code> (see <code class="func">Legendre</code> (<a href="chap15.html#X81464ABF7F10E544"><span class="RefLink">15.4-2</span></a>)). If <var class="Arg">m</var> has <span class="SimpleMath">r</span> different prime factors then there are <span class="SimpleMath">2^r</span> different roots of <var class="Arg">n</var> mod <var class="Arg">m</var>. It is unspecified which one <code class="func">RootMod</code> returns. You can, however, use <code class="func">RootsMod</code> (<a href="chap15.html#X84D3F03B862841F8"><span class="RefLink">15.4-4</span></a>) to compute the full set of roots.</p>
<p><code class="func">RootMod</code> is efficient even for large values of <var class="Arg">m</var>, in fact the most time is usually spent factoring <var class="Arg">m</var> (see <code class="func">FactorsInt</code> (<a href="chap14.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput"># note 'RootMod' does not return 8 in this case but -8:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RootMod( 64, 1009 );</span>
1001
<span class="GAPprompt">gap></span> <span class="GAPinput">RootMod( 64, 3, 1009 );</span>
518
<span class="GAPprompt">gap></span> <span class="GAPinput">RootMod( 64, 5, 1009 );</span>
656
<span class="GAPprompt">gap></span> <span class="GAPinput">List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> x -> x mod 1009 ); # set of all square roots of 64 mod 1009</span>
[ 1001, 8 ]
</pre></div>
<p><a id="X84D3F03B862841F8" name="X84D3F03B862841F8"></a></p>
<h5>15.4-4 RootsMod</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RootsMod</code>( <var class="Arg">n</var>[, <var class="Arg">k</var>], <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">RootsMod</code> computes the set of <var class="Arg">k</var>th roots of the integer <var class="Arg">n</var> modulo the positive integer <var class="Arg">m</var>, i.e., the list of all <span class="SimpleMath">r</span> such that <span class="SimpleMath">r^<var class="Arg">k</var> ≡ <var class="Arg">n</var> mod <var class="Arg">m</var></span>. If only the arguments <var class="Arg">n</var> and <var class="Arg">m</var> are given, the default value for <var class="Arg">k</var> is <span class="SimpleMath">2</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RootsMod( 1, 7*31 ); # the same as `RootsUnityMod( 7*31 )'
[ 1, 92, 125, 216 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RootsMod( 7, 7*31 );</span>
[ 21, 196 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RootsMod( 5, 7*31 );</span>
[ ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RootsMod( 1, 5, 7*31 );</span>
[ 1, 8, 64, 78, 190 ]
</pre></div>
<p><a id="X81F856E682A8ECBA" name="X81F856E682A8ECBA"></a></p>
<h5>15.4-5 RootsUnityMod</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RootsUnityMod</code>( [<var class="Arg">k</var>, ]<var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">RootsUnityMod</code> returns the set of <var class="Arg">k</var>-th roots of unity modulo the positive integer <var class="Arg">m</var>, i.e., the list of all solutions <span class="SimpleMath">r</span> of <span class="SimpleMath">r^<var class="Arg">k</var> ≡ <var class="Arg">n</var> mod <var class="Arg">m</var></span>. If only the argument <var class="Arg">m</var> is given, the default value for <var class="Arg">k</var> is <span class="SimpleMath">2</span>.</p>
<p>In general there are <span class="SimpleMath"><var class="Arg">k</var>^n</span> such roots if the modulus <var class="Arg">m</var> has <span class="SimpleMath">n</span> different prime factors <span class="SimpleMath">p</span> such that <span class="SimpleMath">p ≡ 1 mod <var class="Arg">k</var></span>. If <span class="SimpleMath"><var class="Arg">k</var>^2</span> divides <var class="Arg">m</var> then there are <span class="SimpleMath"><var class="Arg">k</var>^{n+1}</span> such roots; and especially if <span class="SimpleMath"><var class="Arg">k</var> = 2</span> and 8 divides <var class="Arg">m</var> there are <span class="SimpleMath">2^{n+2}</span> such roots.</p>
<p>In the current implementation <var class="Arg">k</var> must be a prime.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RootsUnityMod( 7*31 ); RootsUnityMod( 3, 7*31 );</span>
[ 1, 92, 125, 216 ]
[ 1, 25, 32, 36, 67, 149, 156, 191, 211 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RootsUnityMod( 5, 7*31 );</span>
[ 1, 8, 64, 78, 190 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> x -> x mod 1009 ); # set of all square roots of 64 mod 1009</span>
[ 1001, 8 ]
</pre></div>
<p><a id="X7B3A5A0378A32F83" name="X7B3A5A0378A32F83"></a></p>
<h4>15.5 <span class="Heading">Multiplicative Arithmetic Functions</span></h4>
<p><a id="X823707DF821E79A0" name="X823707DF821E79A0"></a></p>
<h5>15.5-1 Sigma</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Sigma</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">Sigma</code> returns the sum of the positive divisors of the nonzero integer <var class="Arg">n</var>.</p>
<p><code class="func">Sigma</code> is a multiplicative arithmetic function, i.e., if <span class="SimpleMath">n</span> and <span class="SimpleMath">m</span> are relatively prime we have that <span class="SimpleMath">σ(n ⋅ m) = σ(n) σ(m)</span>.</p>
<p>Together with the formula <span class="SimpleMath">σ(p^k) = (p^{k+1}-1) / (p-1)</span> this allows us to compute <span class="SimpleMath">σ(<var class="Arg">n</var>)</span>.</p>
<p>Integers <var class="Arg">n</var> for which <span class="SimpleMath">σ(<var class="Arg">n</var>) = 2 <var class="Arg">n</var></span> are called perfect. Even perfect integers are exactly of the form <span class="SimpleMath">2^{<var class="Arg">n</var>-1}(2^<var class="Arg">n</var>-1)</span> where <span class="SimpleMath">2^<var class="Arg">n</var>-1</span> is prime. Primes of the form <span class="SimpleMath">2^<var class="Arg">n</var>-1</span> are called <em>Mersenne primes</em>, and 42 among the known Mersenne primes are obtained for <var class="Arg">n</var> <span class="SimpleMath">=</span> 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583 and 25964951. Please find more up to date information about Mersenne primes at <span class="URL"><a href="https://www.mersenne.org">https://www.mersenne.org</a></span>. It is not known whether odd perfect integers exist, however <a href="chapBib.html#biBBC89">[BC89]</a> show that any such integer must have at least 300 decimal digits.</p>
<p><code class="func">Sigma</code> usually spends most of its time factoring <var class="Arg">n</var> (see <code class="func">FactorsInt</code> (<a href="chap14.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Sigma( 1 );</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">Sigma( 1009 ); # 1009 is a prime</span>
1010
<span class="GAPprompt">gap></span> <span class="GAPinput">Sigma( 8128 ) = 2*8128; # 8128 is a perfect number</span>
true
</pre></div>
<p><a id="X798C62847EE0372E" name="X798C62847EE0372E"></a></p>
<h5>15.5-2 Tau</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Tau</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">Tau</code> returns the number of the positive divisors of the nonzero integer <var class="Arg">n</var>.</p>
<p><code class="func">Tau</code> is a multiplicative arithmetic function, i.e., if <span class="SimpleMath">n</span> and <span class="SimpleMath">m</span> are relative prime we have <span class="SimpleMath">τ(n ⋅ m) = τ(n) τ(m)</span>. Together with the formula <span class="SimpleMath">τ(p^k) = k+1</span> this allows us to compute <span class="SimpleMath">τ(<var class="Arg">n</var>)</span>.</p>
<p><code class="func">Tau</code> usually spends most of its time factoring <var class="Arg">n</var> (see <code class="func">FactorsInt</code> (<a href="chap14.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Tau( 1 );</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">Tau( 1013 ); # thus 1013 is a prime</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">Tau( 8128 );</span>
14
<span class="GAPprompt">gap></span> <span class="GAPinput"># result is odd if and only if argument is a perfect square:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Tau( 36 );</span>
9
</pre></div>
<p><a id="X79C1DA36827C2959" name="X79C1DA36827C2959"></a></p>
<h5>15.5-3 MoebiusMu</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MoebiusMu</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">MoebiusMu</code> computes the value of Moebius inversion function for the nonzero integer <var class="Arg">n</var>. This is 0 for integers which are not squarefree, i.e., which are divided by a square <span class="SimpleMath">r^2</span>. Otherwise it is 1 if <var class="Arg">n</var> has a even number and <span class="SimpleMath">-1</span> if <var class="Arg">n</var> has an odd number of prime factors.</p>
<p>The importance of <span class="SimpleMath">μ</span> stems from the so called inversion formula. Suppose <span class="SimpleMath">f</span> is a multiplicative arithmetic function defined on the positive integers and let <span class="SimpleMath">g(n) = ∑_{d ∣ n} f(d)</span>. Then <span class="SimpleMath">f(n) = ∑_{d ∣ n} μ(d) g(n/d)</span>. As a special case we have <span class="SimpleMath">ϕ(n) = ∑_{d ∣ n} μ(d) n/d</span> since <span class="SimpleMath">n = ∑_{d ∣ n} ϕ(d)</span> (see <code class="func">Phi</code> (<a href="chap15.html#X85A0C67982D9057A"><span class="RefLink">15.2-2</span></a>)).</p>
<p><code class="func">MoebiusMu</code> usually spends all of its time factoring <var class="Arg">n</var> (see <code class="func">FactorsInt</code> (<a href="chap14.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">MoebiusMu( 60 ); MoebiusMu( 61 ); MoebiusMu( 62 );</span>
0
-1
1
</pre></div>
<p><a id="X7B2E061C835159B9" name="X7B2E061C835159B9"></a></p>
<h4>15.6 <span class="Heading">Continued Fractions</span></h4>
<p><a id="X874C161B83416092" name="X874C161B83416092"></a></p>
<h5>15.6-1 ContinuedFractionExpansionOfRoot</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ContinuedFractionExpansionOfRoot</code>( <var class="Arg">f</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The first <var class="Arg">n</var> terms of the continued fraction expansion of the only positive real root of the polynomial <var class="Arg">f</var> with integer coefficients. The leading coefficient of <var class="Arg">f</var> must be positive and the value of <var class="Arg">f</var> at 0 must be negative. If the degree of <var class="Arg">f</var> is 2 and <var class="Arg">n</var> = 0, the function computes one period of the continued fraction expansion of the root in question. Anything may happen if <var class="Arg">f</var> has three or more positive real roots.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Indeterminate(Integers);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ContinuedFractionExpansionOfRoot(x^2-7,20);</span>
[ 2, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ContinuedFractionExpansionOfRoot(x^2-7,0);</span>
[ 2, 1, 1, 1, 4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ContinuedFractionExpansionOfRoot(x^3-2,20);</span>
[ 1, 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 12, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ContinuedFractionExpansionOfRoot(x^5-x-1,50);</span>
[ 1, 5, 1, 42, 1, 3, 24, 2, 2, 1, 16, 1, 11, 1, 1, 2, 31, 1, 12, 5,
1, 7, 11, 1, 4, 1, 4, 2, 2, 3, 4, 2, 1, 1, 11, 1, 41, 12, 1, 8, 1,
1, 1, 1, 1, 9, 2, 1, 5, 4 ]
</pre></div>
<p><a id="X8059667580A039A6" name="X8059667580A039A6"></a></p>
<h5>15.6-2 ContinuedFractionApproximationOfRoot</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ContinuedFractionApproximationOfRoot</code>( <var class="Arg">f</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The <var class="Arg">n</var>th continued fraction approximation of the only positive real root of the polynomial <var class="Arg">f</var> with integer coefficients. The leading coefficient of <var class="Arg">f</var> must be positive and the value of <var class="Arg">f</var> at 0 must be negative. Anything may happen if <var class="Arg">f</var> has three or more positive real roots.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ContinuedFractionApproximationOfRoot(x^2-2,10);</span>
3363/2378
<span class="GAPprompt">gap></span> <span class="GAPinput">3363^2-2*2378^2;</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">z := ContinuedFractionApproximationOfRoot(x^5-x-1,20);</span>
499898783527/428250732317
<span class="GAPprompt">gap></span> <span class="GAPinput">z^5-z-1;</span>
486192462527432755459620441970617283/
14404247382319842421697357558805709031116987826242631261357
</pre></div>
<p><a id="X7C5563A37D566DA5" name="X7C5563A37D566DA5"></a></p>
<h4>15.7 <span class="Heading">Miscellaneous</span></h4>
<p><a id="X8243EAA586D78ED4" name="X8243EAA586D78ED4"></a></p>
<h5>15.7-1 PValuation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PValuation</code>( <var class="Arg">n</var>, <var class="Arg">p</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For an integer <var class="Arg">n</var> and a prime <var class="Arg">p</var> this function returns the <var class="Arg">p</var>-valuation of <var class="Arg">n</var>, that is the exponent <span class="SimpleMath">e</span> such that <span class="SimpleMath">p^e</span> is the largest power of <var class="Arg">p</var> that divides <var class="Arg">n</var>. The valuation of zero is infinity.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PValuation(100,2);</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">PValuation(100,3);</span>
0
</pre></div>
<p><a id="X85E1EFC484F648A4" name="X85E1EFC484F648A4"></a></p>
<h5>15.7-2 TwoSquares</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TwoSquares</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">TwoSquares</code> returns a list of two integers <span class="SimpleMath">x ≤ y</span> such that the sum of the squares of <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> is equal to the nonnegative integer <var class="Arg">n</var>, i.e., <span class="SimpleMath">n = x^2 + y^2</span>. If no such representation exists <code class="func">TwoSquares</code> will return <code class="keyw">fail</code>. <code class="func">TwoSquares</code> will return a representation for which the gcd of <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> is as small as possible. It is not specified which representation <code class="func">TwoSquares</code> returns if there is more than one.</p>
<p>Let <span class="SimpleMath">a</span> be the product of all maximal powers of primes of the form <span class="SimpleMath">4k+3</span> dividing <var class="Arg">n</var>. A representation of <var class="Arg">n</var> as a sum of two squares exists if and only if <span class="SimpleMath">a</span> is a perfect square. Let <span class="SimpleMath">b</span> be the maximal power of <span class="SimpleMath">2</span> dividing <var class="Arg">n</var> or its half, whichever is a perfect square. Then the minimal possible gcd of <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> is the square root <span class="SimpleMath">c</span> of <span class="SimpleMath">a ⋅ b</span>. The number of different minimal representation with <span class="SimpleMath">x ≤ y</span> is <span class="SimpleMath">2^{l-1}</span>, where <span class="SimpleMath">l</span> is the number of different prime factors of the form <span class="SimpleMath">4k+1</span> of <var class="Arg">n</var>.</p>
<p>The algorithm first finds a square root <span class="SimpleMath">r</span> of <span class="SimpleMath">-1</span> modulo <span class="SimpleMath"><var class="Arg">n</var> / (a ⋅ b)</span>, which must exist, and applies the Euclidean algorithm to <span class="SimpleMath">r</span> and <var class="Arg">n</var>. The first residues in the sequence that are smaller than <span class="SimpleMath">sqrt{<var class="Arg">n</var>/(a ⋅ b)}</span> times <span class="SimpleMath">c</span> are a possible pair <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span>.</p>
<p>Better descriptions of the algorithm and related topics can be found in <a href="chapBib.html#biBWagon90">[Wag90]</a> and <a href="chapBib.html#biBZagier90">[Zag90]</a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">TwoSquares( 5 );</span>
[ 1, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">TwoSquares( 11 ); # there is no representation</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">TwoSquares( 16 );</span>
[ 0, 4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"># 3 is the minimal possible gcd because 9 divides 45:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">TwoSquares( 45 );</span>
[ 3, 6 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"># it is not [5,10] because their gcd is not minimal:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">TwoSquares( 125 );</span>
[ 2, 11 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"># [10,11] would be the other possible representation:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">TwoSquares( 13*17 );</span>
[ 5, 14 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">TwoSquares( 848654483879497562821 ); # argument is prime</span>
[ 6305894639, 28440994650 ]
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap14.html">[Previous Chapter]</a> <a href="chap16.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chap19.html">19</a> <a href="chap20.html">20</a> <a href="chap21.html">21</a> <a href="chap22.html">22</a> <a href="chap23.html">23</a> <a href="chap24.html">24</a> <a href="chap25.html">25</a> <a href="chap26.html">26</a> <a href="chap27.html">27</a> <a href="chap28.html">28</a> <a href="chap29.html">29</a> <a href="chap30.html">30</a> <a href="chap31.html">31</a> <a href="chap32.html">32</a> <a href="chap33.html">33</a> <a href="chap34.html">34</a> <a href="chap35.html">35</a> <a href="chap36.html">36</a> <a href="chap37.html">37</a> <a href="chap38.html">38</a> <a href="chap39.html">39</a> <a href="chap40 | | |
