<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">\(\phi(m)\)</span> (see <code class="func">Phi</code> (<a href="chap15_mj.html#X85A0C67982D9057A"><spanclass="RefLink">15.2-2</span></a>)), and <span class="SimpleMath">\(\lambda(m)\)</span> (see <code class="func">Lambda</code> (<a href="chap15_mj.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">\(\phi(m)\)</span>, are called <em>primitive roots</em> (see <code class="func">PrimitiveRootMod</code> (<a href="chap15_mj.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_mj.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">\(\phi(\textit{m})\)</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}} \cdots p_k^{{e_k}}\)</span>. Then <span class="SimpleMath">\(\phi(m)\)</span> is <span class="SimpleMath">\(p_1^{{e_1-1}} (p_1-1) p_2^{{e_2-1}} (p_2-1) \cdots 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">\(\lambda(\textit{m})\)</span> of the group of prime residues modulo the integer <var class="Arg">m</var>.</p>
<p><span class="SimpleMath">\(\lambda(\textit{m})\)</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 \equiv 1 \pmod{\textit{m}}\)</span>. Fermat's theorem asserts \(a^{{\phi(\textit{m})}} \equiv 1 \pmod{\textit{m}}\); thus \(\lambda(\textit{m})\) divides \(\phi(\textit{m})\) (see Phi (15.2-2)).
<p>Carmichael's theorem states that \(\lambda\) can be computed as follows: \(\lambda(2) = 1\), \(\lambda(4) = 2\) and \(\lambda(2^e) = 2^{{e-2}}\) if \(3 \leq e\), \(\lambda(p^e) = (p-1) p^{{e-1}}\) (i.e. \(\phi(m)\)) if \(p\) is an odd prime and \(\lambda(m*n) = \)Lcm\(( \lambda(m), \lambda(n) )\) if \(m, n\) are coprime.
<p>Composites for which <span class="SimpleMath">\(\lambda(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">\(\textit{n}^i \equiv 1 \pmod{\textit{m}}\)</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_mj.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">\(\lambda(\textit{m})\)</span> (see <code class="func">Lambda</code> (<a href="chap15_mj.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_mj.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">\(\textit{r}^{\textit{l}} \equiv \textit{n} \pmod{\textit{m}}\)</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_mj.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><spanclass="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(\sqrt{\textit{m}})\) space and time). Otherwise let m\( = r l\) and \(e = a + b r\)with \(0 \leq a < r\). Then \(a =\)DLog\((\textit{base}^l, \textit{x}^l, r)\) and\(b = \)DLog\((\textit{base}^r, \textit{x}/\textit{base}^a, l)\).
<p>This function is used for a method of <code class="func">LogFFE</code> (<a href="chap59_mj.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(\textit{n},\textit{m})\)</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_mj.html#X81464ABF7F10E544"><span class="RefLink">15.4-2</span></a>)).</p>
<p>For the general case suppose that <span class="SimpleMath">\(m = p_1 \cdot p_2 \cdots 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) \cdot J(n,p_2) \cdots 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_mj.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 \equiv n \pmod{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_mj.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_mj.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_mj.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_mj.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^{\textit{k}} \equiv \textit{n} \pmod{\textit{m}}\)</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_mj.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_mj.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_mj.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^{\textit{k}} \equiv \textit{n} \pmod{\textit{m}}\)</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^{\textit{k}} \equiv \textit{n} \pmod{\textit{m}}\)</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">\(\textit{k}^n\)</span> such roots if the modulus <var class="Arg">m</var> has <span class="SimpleMath">\(n\)</span> different prime factors <spanclass="SimpleMath">\(p\)</span> such that <span class="SimpleMath">\(p \equiv 1 \pmod{\textit{k}}\)</span>. If <span class="SimpleMath">\(\textit{k}^2\)</span> divides <var class="Arg">m</var> then there are <span class="SimpleMath">\(\textit{k}^{{n+1}}\)</span> such roots; and especially if <span class="SimpleMath">\(\textit{k} = 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 <span class="SimpleMath">\(\sigma(n \cdot m) = \sigma(n) \sigma(m)\)</span>.</p>
<p>Together with the formula <span class="SimpleMath">\(\sigma(p^k) = (p^{{k+1}}-1) / (p-1)\)</span> this allows us to compute <span class="SimpleMath">\(\sigma(\textit{n})\)</span>.</p>
<p>Integers <var class="Arg">n</var> for which <span class="SimpleMath">\(\sigma(\textit{n}) = 2 \textit{n}\)</span> are called perfect. Even perfect integers are exactly of the form <span class="SimpleMath">\(2^{{\textit{n}-1}}(2^{\textit{n}}-1)\)</span> where <span class="SimpleMath">\(2^{\textit{n}}-1\)</span> is prime. Primes of the form <span class="SimpleMath">\(2^{\textit{n}}-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_mj.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_mj.html#X82C989DB84744B36"><spanclass="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 <spanclass="SimpleMath">\(\tau(n \cdot m) = \tau(n) \tau(m)\)</span>. Together with the formula <span class="SimpleMath">\(\tau(p^k) = k+1\)</span> this allows us to compute <span class="SimpleMath">\(\tau(\textit{n})\)</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_mj.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">\(\mu\)</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) = \sum_{{d \mid n}} f(d)\)</span>. Then <span class="SimpleMath">\(f(n) = \sum_{{d \mid n}} \mu(d) g(n/d)\)</span>. As a special case we have <span class="SimpleMath">\(\phi(n) = \sum_{{d \mid n}} \mu(d) n/d\)</span> since <span class="SimpleMath">\(n = \sum_{{d \mid n}} \phi(d)\)</span> (see <code class="func">Phi</code> (<a href="chap15_mj.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_mj.html#X82C989DB84744B36"><span class="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 \leq y\)</span> such that the sum of the squares of <span class="SimpleMath">\(x\)</span> and <spanclass="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 \cdot b\)</span>. The number of different minimal representation with <span class="SimpleMath">\(x \leq 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">\(\textit{n} / (a \cdot 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{{\textit{n}/(a \cdot 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_mj.html#biBWagon90">[Wag90]</a> and <a href="chapBib_mj.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.
