<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>
<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>
<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="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>
<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="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>
<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 <varclass="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"><spanclass="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>
<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><tdclass="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="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="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>
<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>
<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>
<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>
<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>
<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="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>
<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 <spanclass="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>
<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>
<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"><spanclass="RefLink">14.4-7</span></a>)).</p>
<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><tdclass="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="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="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="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>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
