|
|
|
|
Quelle chap14_mj.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/doc/ref/chap14_mj.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>
< script type= "text/javascript"
src= "https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< title>GAP (ref) - Chapter 14: Integers</ 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= "chap14" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span><a href= "chap0_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chap17_mj.html">17</a> <a href="chap18_mj.html">18</a> <a href="chap19_mj.html">19</a> <a href="chap20_mj.html">20</a> <a href="chap21_mj.html">21</a> <a href="chap22_mj.html">22</a> <a href="chap23_mj.html">23</a> <a href="chap24_mj.html">24</a> <a href="chap25_mj.html">25</a> <a href="chap26_mj.html">26</a> <a href="chap27_mj.html">27</a> <a href="chap28_mj.html">28</a> <a href="chap29_mj.html">29</a> <a href="chap30_mj.html">30</a> <a href="chap31_mj.html">31</a> <a href="chap32_mj.html">32</a> <a href="chap33_mj.html">33</a> <a href="chap34_mj.html">34</a> <a href="chap35_mj.html">35</a> <a href="chap36_mj.html">36</a> <a href="chap37_mj.html">37</a> <a href="chap38_mj.html">38</a> <a href="chap39_mj.html">39</a> <a href="chap40_mj.html">40</a> <a href="chap41_mj.html">41</a> <a href="chap42_mj.html">42</a> <a href="chap43_mj.html">43</a> <a href="chap44_mj.html">44</a> <a href="chap45_mj.html">45</a> <a href="chap46_mj.html">46</a> <a href="chap47_mj.html">47</a> <a href="chap48_mj.html">48</a> <a href="chap49_mj.html">49</a> <a href="chap50_mj.html">50</a> <a href="chap51_mj.html">51</a> <a href="chap52_mj.html">52</a> <a href="chap53_mj.html">53</a> <a href="chap54_mj.html">54</a> <a href="chap55_mj.html">55</a> <a href="chap56_mj.html">56</a> <a href="chap57_mj.html">57</a> <a href="chap58_mj.html">58</a> <a href="chap59_mj.html">59</a> <a href="chap60_mj.html">60</a> <a href="chap61_mj.html">61</a> <a href="chap62_mj.html">62</a> <a href="chap63_mj.html">63</a> <a href="chap64_mj.html">64</a> <a href="chap65_mj.html">65</a> <a href="chap66_mj.html">66</a> <a href="chap67_mj.html">67</a> <a href="chap68_mj.html">68</a> <a href="chap69_mj.html">69</a> <a href="chap70_mj.html">70</a> <a href="chap71_mj.html">71</a> <a href="chap72_mj.html">72</a> <a href="chap73_mj.html">73</a> <a href="chap74_mj.html">74</a> <a href="chap75_mj.html">75</a> <a href="chap76_mj.html">76</a> <a href="chap77_mj.html">77</a> <a href="chap78_mj.html">78</a> <a href="chap79_mj.html">79</a> <a href="chap80_mj.html">80</a> <a href="chap81_mj.html">81</a> <a href="chap82_mj.html">82</a> <a href="chap83_mj.html">83</a> <a href="chap84_mj.html">84</a> <a href="chap85_mj.html">85</a> <a href="chap86_mj.html">86</a> <a href="chap87_mj.html">87</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap13_mj.html">[Previous Chapter]</a> <a href="chap15_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap14.html">[MathJax off]</a></p>
<p><a id="X853DF11B80068ED5" name="X853DF11B80068ED5"></a></p>
<div class="ChapSects"><a href="chap14_mj.html#X853DF11B80068ED5">14 <span class="Heading">Integers</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X838230CE810107A3">14.1 <span class="Heading">Integers: Global Variables</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7E20D82B79DE5129">14.1-1 Integers</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X818683B17F8C97F3">14.1-2 IsIntegers</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X80CF510B8080C7CA">14.2 <span class="Heading">Elementary Operations for Integers</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X87AEADF07DC8303B">14.2-1 IsInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X82A854757DFA9C76">14.2-2 IsPosInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X87CA734380B5F68C">14.2-3 Int</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X87DD1EEE7EF18036">14.2-4 IsEvenInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X8621BA927CD12EFB">14.2-5 IsOddInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X782095927FB9F1DB">14.2-6 AbsInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X842614817FE48D62">14.2-7 SignInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X8197C4E882BAF14E">14.2-8 LogInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X83D9B5C87EEA2A77">14.2-9 RootInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7F98A0CE7B9FD366">14.2-10 SmallestRootInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X83B998E486893FED">14.2-11 IsSquareInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X862D1BD786EFFDA9">14.2-12 ListOfDigits</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X8185784B7E228DEA">14.2-13 Random</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X7A9FD25D81D88D1B">14.3 <span class="Heading">Quotients and Remainders</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X849D0F807F697D35">14.3-1 QuoInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X795170A385AC8FEE">14.3-2 BestQuoInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X805ADD5A826D844D">14.3-3 RemInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7A4FEFCA8128E3C3">14.3-4 GcdInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X8775930486BD0C5B">14.3-5 Gcdex</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7B33143E78A8DDE3">14.3-6 LcmInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X79B466E984CD52D4">14.3-7 CoefficientsQadic</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X83124F86839DC7E6">14.3-8 CoefficientsMultiadic</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X84A1900E82902B5F">14.3-9 ChineseRem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7E404B1183DBC82A">14.3-10 PowerModInt</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X82005E587F0CB02A">14.4 <span class="Heading">Prime Integers and Factorization</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X86F5E4CD82FEB9F4">14.4-1 Primes</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X78FDA4437EDCA70C">14.4-2 IsPrimeInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7CD977B17B4A7A4B">14.4-3 PrimalityProof</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X8443125D7FD6F2A6">14.4-4 IsPrimePowerInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X78744C367A94C69F">14.4-5 NextPrimeInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X819060E17E83728A">14.4-6 PrevPrimeInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X82C989DB84744B36">14.4-7 FactorsInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X80E7A5D381C64CC9">14.4-8 PrimeDivisors</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X786FF92C7C54BF97">14.4-9 PartialFactorization</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X803D431087B6FF28">14.4-10 PrintFactorsInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X82148B347E294C87">14.4-11 PrimePowersInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X809E0E1B83AF7695">14.4-12 DivisorsInt</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X864BF040862409FC">14.5 <span class="Heading">Residue Class Rings</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X87B1210B8581D5B2"><code>14.5-1 \mod</code></a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X79CE76AD82B3E2B2">14.5-2 ZmodnZ</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X838F36507D985EDA">14.5-3 ZmodnZObj</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7D0107DD79753901">14.5-4 IsZmodnZObj</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X7904B6D681EBF091">14.6 <span class="Heading">Check Digits</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X82BABA8F868BD425">14.6-1 CheckDigitISBN</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X85F1A6A5870485B9">14.6-2 CheckDigitTestFunction</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X85361FAE8088C006">14.7 <span class="Heading">Random Sources</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X82E31A697E389F1D">14.7-1 IsRandomSource</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X821004F286282D49">14.7-2 Random</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X86FFFBC9790F9742">14.7-3 <span class="Heading">State and Reset for Random Sources</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7AC96008820FAF1F">14.7-4 <span class="Heading">Kinds of Random Sources</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X7CB0B5BC82F8FD8F">14.7-5 RandomSource</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X8653AE447D94C1DC">14.7-6 <span class="Heading">Implementing new kinds of random sources</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X7A0311DF78DB4FD8">14.8 <span class="Heading">Bitfields</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X85C7BD9E7FCC6C10">14.8-1 MakeBitfields</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14_mj.html#X8068CE3781F4003C">14.8-2 BuildBitfields</a></span>
</div></div>
</div>
<h3>14 <span class="Heading">Integers</span></h3>
<p>One of the most fundamental datatypes in every programming language is the integer type. <strong class="pkg">GAP</strong> is no exception.</p>
<p><strong class="pkg">GAP</strong> integers are entered as a sequence of decimal digits optionally preceded by a <q><code class="code">+</code></q> sign for positive integers or a <q><code class="code">-</code></q> sign for negative integers. The size of integers in <strong class="pkg">GAP</strong> is only limited by the amount of available memory, so you can compute with integers having thousands of digits.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">-1234;</span>
-1234
<span class="GAPprompt">gap></span> <span class="GAPinput">123456789012345678901234567890123456789012345678901234567890;</span>
123456789012345678901234567890123456789012345678901234567890
</pre></div>
<p>Note that in a few places, only certain small integer values can be used. A <em>small integer</em> (also referred to as <em>immediate integer</em>) is an integer <span class="SimpleMath">\(n\)</span> satisfying <code class="code">INTOBJ_MIN</code> <span class="SimpleMath">\( \leq n \leq \)</span> <code class="code">INTOBJ_MAX</code>, where <code class="code">INTOBJ_MIN</code> and <code class="code">INTOBJ_MAX</code> equal either <span class="SimpleMath">\(-2^{28}\)</span> and <span class="SimpleMath">\(2^{28}-1\)</span> (on 32-bit systems) or <span class="SimpleMath">\(-2^{60}\)</span> and <span class="SimpleMath">\(2^{60}-1\)</span> (on 64-bit systems). For example, the elements of a range are restricted to small integers (see <a href="chap21_mj.html#X79596BDE7CAF8491"><span class="RefLink">21.22</span></a>).</p>
<p>Many more functions that are mainly related to the prime residue group of integers modulo an integer are described in chapter <a href="chap15_mj.html#X7FB995737B7ED8A2"><span class="RefLink">15</span></a>, and functions dealing with combinatorics can be found in chapter <a href="chap16_mj.html#X7BDA99EE7CEADA7C"><span class="RefLink">16</span></a>.</p>
<p><a id="X838230CE810107A3" name="X838230CE810107A3"></a></p>
<h4>14.1 <span class="Heading">Integers: Global Variables</span></h4>
<p><a id="X7E20D82B79DE5129" name="X7E20D82B79DE5129"></a></p>
<h5>14.1-1 Integers</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Integers</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositiveIntegers</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NonnegativeIntegers</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>These global variables represent the ring of integers and the semirings of positive and nonnegative integers, respectively.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size( Integers ); 2 in Integers;</span>
infinity
true
</pre></div>
<p><code class="func">Integers</code> is a subset of <code class="func">Rationals</code> (<a href="chap17_mj.html#X7B6029D18570C08A"><span class="RefLink">17.1-1</span></a>), which is a subset of <code class="func">Cyclotomics</code> (<a href="chap18_mj.html#X863D1E017BC9EB7F"><span class="RefLink">18.1-2</span></a>). See Chapter <a href="chap18_mj.html#X7DFC03C187DE4841"><span class="RefLink">18</span></a> for arithmetic operations and comparison of integers.</p>
<p><a id="X818683B17F8C97F3" name="X818683B17F8C97F3"></a></p>
<h5>14.1-2 IsIntegers</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsIntegers</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPositiveIntegers</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsNonnegativeIntegers</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>are the defining categories for the domains <code class="func">Integers</code> (<a href="chap14_mj.html#X7E20D82B79DE5129"><span class="RefLink">14.1-1</span></a>), <code class="func">PositiveIntegers</code> (<a href="chap14_mj.html#X7E20D82B79DE5129"><span class="RefLink">14.1-1</span></a>), and <code class="func">NonnegativeIntegers</code> (<a href="chap14_mj.html#X7E20D82B79DE5129"><span class="RefLink">14.1-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIntegers( Integers ); IsIntegers( Rationals ); IsIntegers( 7 );</span>
true
false
false
</pre></div>
<p><a id="X80CF510B8080C7CA" name="X80CF510B8080C7CA"></a></p>
<h4>14.2 <span class="Heading">Elementary Operations for Integers</span></h4>
<p><a id="X87AEADF07DC8303B" name="X87AEADF07DC8303B"></a></p>
<h5>14.2-1 IsInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsInt</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Every rational integer lies in the category <code class="func">IsInt</code>, which is a subcategory of <code class="func">IsRat</code> (<a href="chap17_mj.html#X7ED018F5794935F7"><span class="RefLink">17.2-1</span></a>).</p>
<p><a id="X82A854757DFA9C76" name="X82A854757DFA9C76"></a></p>
<h5>14.2-2 IsPosInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPosInt</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Every positive integer lies in the category <code class="func">IsPosInt</code>.</p>
<p><a id="X87CA734380B5F68C" name="X87CA734380B5F68C"></a></p>
<h5>14.2-3 Int</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Int</code>( <var class="Arg">elm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">Int</code> returns an integer <code class="code">int</code> whose meaning depends on the type of <var class="Arg">elm</var>. For example:</p>
<p>If <var class="Arg">elm</var> is a rational number (see Chapter <a href="chap17_mj.html#X87003045878E74DF"><span class="RefLink">17</span></a>) then <code class="code">int</code> is the integer part of the quotient of numerator and denominator of <var class="Arg">elm</var> (see <code class="func">QuoInt</code> (<a href="chap14_mj.html#X849D0F807F697D35"><span class="RefLink">14.3-1</span></a>)).</p>
<p>If <var class="Arg">elm</var> is an element of a finite prime field (see Chapter <a href="chap59_mj.html#X7893ABF67A028802"><span class="RefLink">59</span></a>) then <code class="code">int</code> is the smallest nonnegative integer such that <code class="code"><var class="Arg">elm</var> = int * One( <var class="Arg">elm</var> )</code>.</p>
<p>If <var class="Arg">elm</var> is a string (see Chapter <a href="chap27_mj.html#X7D28329B7EDB8F47"><span class="RefLink">27</span></a>) consisting entirely of decimal digits <code class="code">'0'</code>, <code class="code">'1'</code>, <span class="SimpleMath">\(\ldots\)</span>, <code class="code">'9'</code>, and optionally a sign <code class="code">'-'</code> (at the first position), then <code class="code">int</code> is the integer described by this string. For all other strings, <code class="code">fail</code> is returned. See <code class="func">Int</code> (<a href="chap27_mj.html#X7B6D118184F692A0"><span class="RefLink">27.9-1</span></a>).</p>
<p>The operation <code class="func">String</code> (<a href="chap27_mj.html#X81FB5BE27903EC32"><span class="RefLink">27.7-6</span></a>) can be used to compute a string for rational integers, in fact for all cyclotomics.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Int( 4/3 ); Int( -2/3 );</span>
1
0
<span class="GAPprompt">gap></span> <span class="GAPinput">int:= Int( Z(5) ); int * One( Z(5) );</span>
2
Z(5)
<span class="GAPprompt">gap></span> <span class="GAPinput">Int( "12345" ); Int( "-27" ); Int( "-27/3" );</span>
12345
-27
fail
</pre></div>
<p><a id="X87DD1EEE7EF18036" name="X87DD1EEE7EF18036"></a></p>
<h5>14.2-4 IsEvenInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEvenInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>tests if the integer <var class="Arg">n</var> is divisible by 2.</p>
<p><a id="X8621BA927CD12EFB" name="X8621BA927CD12EFB"></a></p>
<h5>14.2-5 IsOddInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsOddInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>tests if the integer <var class="Arg">n</var> is not divisible by 2.</p>
<p><a id="X782095927FB9F1DB" name="X782095927FB9F1DB"></a></p>
<h5>14.2-6 AbsInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AbsInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">AbsInt</code> returns the absolute value of the integer <var class="Arg">n</var>, i.e., <var class="Arg">n</var> if <var class="Arg">n</var> is positive, -<var class="Arg">n</var> if <var class="Arg">n</var> is negative and 0 if <var class="Arg">n</var> is 0.</p>
<p><code class="func">AbsInt</code> is a special case of the general operation <code class="func">EuclideanDegree</code> (<a href="chap56_mj.html#X784234088350D4E4"><span class="RefLink">56.6-2</span></a>).</p>
<p>See also <code class="func">AbsoluteValue</code> (<a href="chap18_mj.html#X81DD58BB81FB3426"><span class="RefLink">18.1-8</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AbsInt( 33 );</span>
33
<span class="GAPprompt">gap></span> <span class="GAPinput">AbsInt( -214378 );</span>
214378
<span class="GAPprompt">gap></span> <span class="GAPinput">AbsInt( 0 );</span>
0
</pre></div>
<p><a id="X842614817FE48D62" name="X842614817FE48D62"></a></p>
<h5>14.2-7 SignInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SignInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">SignInt</code> returns the sign of the integer <var class="Arg">n</var>, i.e., 1 if <var class="Arg">n</var> is positive, -1 if <var class="Arg">n</var> is negative and 0 if <var class="Arg">n</var> is 0.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SignInt( 33 );</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">SignInt( -214378 );</span>
-1
<span class="GAPprompt">gap></span> <span class="GAPinput">SignInt( 0 );</span>
0
</pre></div>
<p><a id="X8197C4E882BAF14E" name="X8197C4E882BAF14E"></a></p>
<h5>14.2-8 LogInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LogInt</code>( <var class="Arg">n</var>, <var class="Arg">base</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">LogInt</code> returns the integer part of the logarithm of the positive integer <var class="Arg">n</var> with respect to the positive integer <var class="Arg">base</var>, i.e., the largest positive integer <span class="SimpleMath">\(e\)</span> such that <span class="SimpleMath">\(\textit{base}^e \leq \textit{n}\)</span>. The function <code class="func">LogInt</code> will signal an error if either <var class="Arg">n</var> or <var class="Arg">base</var> is not positive.</p>
<p>For <var class="Arg">base</var> <span class="SimpleMath">\(= 2\)</span> this is very efficient because the internal binary representation of the integer is used.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">LogInt( 1030, 2 );</span>
10
<span class="GAPprompt">gap></span> <span class="GAPinput">2^10;</span>
1024
<span class="GAPprompt">gap></span> <span class="GAPinput">LogInt( 1, 10 );</span>
0
</pre></div>
<p><a id="X83D9B5C87EEA2A77" name="X83D9B5C87EEA2A77"></a></p>
<h5>14.2-9 RootInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RootInt</code>( <var class="Arg">n</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">RootInt</code> returns the integer part of the <var class="Arg">k</var>th root of the integer <var class="Arg">n</var>. If the optional integer argument <var class="Arg">k</var> is not given it defaults to 2, i.e., <code class="func">RootInt</code> returns the integer part of the square root in this case.</p>
<p>If <var class="Arg">n</var> is positive, <code class="func">RootInt</code> returns the largest positive integer <span class="SimpleMath">\(r\)</span> such that <span class="SimpleMath">\(r^{\textit{k}} \leq \textit{n}\)</span>. If <var class="Arg">n</var> is negative and <var class="Arg">k</var> is odd <code class="func">RootInt</code> returns <code class="code">-RootInt( -<var class="Arg">n</var>, <var class="Arg">k</var> )</code>. If <var class="Arg">n</var> is negative and <var class="Arg">k</var> is even <code class="func">RootInt</code> will cause an error. <code class="func">RootInt</code> will also cause an error if <var class="Arg">k</var> is 0 or negative.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RootInt( 361 );</span>
19
<span class="GAPprompt">gap></span> <span class="GAPinput">RootInt( 2 * 10^12 );</span>
1414213
<span class="GAPprompt">gap></span> <span class="GAPinput">RootInt( 17000, 5 );</span>
7
<span class="GAPprompt">gap></span> <span class="GAPinput">7^5;</span>
16807
</pre></div>
<p><a id="X7F98A0CE7B9FD366" name="X7F98A0CE7B9FD366"></a></p>
<h5>14.2-10 SmallestRootInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallestRootInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">SmallestRootInt</code> returns the smallest root of the integer <var class="Arg">n</var>.</p>
<p>The smallest root of an integer <var class="Arg">n</var> is the integer <span class="SimpleMath">\(r\)</span> of smallest absolute value for which a positive integer <span class="SimpleMath">\(k\)</span> exists such that <span class="SimpleMath">\(\textit{n} = r^k\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestRootInt( 2^30 );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestRootInt( -(2^30) );</span>
-4
</pre></div>
<p>Note that <span class="SimpleMath">\((-2)^{30} = +(2^{30})\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestRootInt( 279936 );</span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">LogInt( 279936, 6 );</span>
7
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestRootInt( 1001 );</span>
1001
</pre></div>
<p><a id="X83B998E486893FED" name="X83B998E486893FED"></a></p>
<h5>14.2-11 IsSquareInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSquareInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IsSquareInt</code> tests whether the integer <var class="Arg">n</var> is the square of an integer or not. This test is much faster than the simpler <code class="code">RootInt</code><span class="SimpleMath">\((n)^2=n\)</span> because it first tests whether <var class="Arg">n</var> is a square residue modulo some small integers.</p>
<p><a id="X862D1BD786EFFDA9" name="X862D1BD786EFFDA9"></a></p>
<h5>14.2-12 ListOfDigits</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ListOfDigits</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For a positive integer <var class="Arg">n</var> this function returns a list <var class="Arg">l</var>, consisting of the digits of <var class="Arg">n</var> in decimal representation.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ListOfDigits(3142);</span>
[ 3, 1, 4, 2 ]
</pre></div>
<p><a id="X8185784B7E228DEA" name="X8185784B7E228DEA"></a></p>
<h5>14.2-13 Random</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Random</code>( <var class="Arg">Integers</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><code class="func">Random</code> for integers returns pseudo random integers between <span class="SimpleMath">\(-10\)</span> and <span class="SimpleMath">\(10\)</span> distributed according to a binomial distribution. To generate uniformly distributed integers from a range, use the construction <code class="code">Random( [ <var class="Arg">low</var> .. <var class="Arg">high</var> ] )</code> (see <code class="func">Random</code> (<a href="chap30_mj.html#X7FF906E57D6936F8"><span class="RefLink">30.7-1</span></a>)).</p>
<p><a id="X7A9FD25D81D88D1B" name="X7A9FD25D81D88D1B"></a></p>
<h4>14.3 <span class="Heading">Quotients and Remainders</span></h4>
<p><a id="X849D0F807F697D35" name="X849D0F807F697D35"></a></p>
<h5>14.3-1 QuoInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QuoInt</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">QuoInt</code> returns the integer part of the quotient of its integer operands.</p>
<p>If <var class="Arg">n</var> and <var class="Arg">m</var> are positive, <code class="func">QuoInt</code> returns the largest positive integer <span class="SimpleMath">\(q\)</span> such that <span class="SimpleMath">\(q * \textit{m} \leq \textit{n}\)</span>. If <var class="Arg">n</var> or <var class="Arg">m</var> or both are negative the absolute value of the integer part of the quotient is the quotient of the absolute values of <var class="Arg">n</var> and <var class="Arg">m</var>, and the sign of it is the product of the signs of <var class="Arg">n</var> and <var class="Arg">m</var>.</p>
<p><code class="func">QuoInt</code> is used in a method for the general operation <code class="func">EuclideanQuotient</code> (<a href="chap56_mj.html#X7A93FA788318B147"><span class="RefLink">56.6-3</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">QuoInt(5,3); QuoInt(-5,3); QuoInt(5,-3); QuoInt(-5,-3);</span>
1
-1
-1
1
</pre></div>
<p><a id="X795170A385AC8FEE" name="X795170A385AC8FEE"></a></p>
<h5>14.3-2 BestQuoInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BestQuoInt</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">BestQuoInt</code> returns the best quotient <span class="SimpleMath">\(q\)</span> of the integers <var class="Arg">n</var> and <var class="Arg">m</var>. This is the quotient such that <span class="SimpleMath">\(\textit{n}-q*\textit{m}\)</span> has minimal absolute value. If there are two quotients whose remainders have the same absolute value, then the quotient with the smaller absolute value is chosen.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">BestQuoInt( 5, 3 ); BestQuoInt( -5, 3 );</span>
2
-2
</pre></div>
<p><a id="X805ADD5A826D844D" name="X805ADD5A826D844D"></a></p>
<h5>14.3-3 RemInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RemInt</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">RemInt</code> returns the remainder of its two integer operands.</p>
<p>If <var class="Arg">m</var> is not equal to zero, <code class="func">RemInt</code> returns <code class="code"><var class="Arg">n</var> - <var class="Arg">m</var> * QuoInt( <var class="Arg">n</var>, <var class="Arg">m</var> )</code>. Note that the rules given for <code class="func">QuoInt</code> (<a href="chap14_mj.html#X849D0F807F697D35"><span class="RefLink">14.3-1</span></a>) imply that the return value of <code class="func">RemInt</code> has the same sign as <var class="Arg">n</var> and its absolute value is strictly less than the absolute value of <var class="Arg">m</var>. Note also that the return value equals <code class="code"><var class="Arg">n</var> mod <var class="Arg">m</var></code> when both <var class="Arg">n</var> and <var class="Arg">m</var> are nonnegative. Dividing by <code class="code">0</code> signals an error.</p>
<p><code class="func">RemInt</code> is used in a method for the general operation <code class="func">EuclideanRemainder</code> (<a href="chap56_mj.html#X7B5E9639865E91BA"><span class="RefLink">56.6-4</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RemInt(5,3); RemInt(-5,3); RemInt(5,-3); RemInt(-5,-3);</span>
2
-2
2
-2
</pre></div>
<p><a id="X7A4FEFCA8128E3C3" name="X7A4FEFCA8128E3C3"></a></p>
<h5>14.3-4 GcdInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GcdInt</code>( <var class="Arg">m</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">GcdInt</code> returns the greatest common divisor of its two integer operands <var class="Arg">m</var> and <var class="Arg">n</var>, i.e., the greatest integer that divides both <var class="Arg">m</var> and <var class="Arg">n</var>. The greatest common divisor is never negative, even if the arguments are. We define <code class="code">GcdInt( <var class="Arg">m</var>, 0 ) = GcdInt( 0, <var class="Arg">m</var> ) = AbsInt( <var class="Arg">m</var> )</code> and <code class="code">GcdInt( 0, 0 ) = 0</code>.</p>
<p><code class="func">GcdInt</code> is a method used by the general function <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">GcdInt( 123, 66 );</span>
3
</pre></div>
<p><a id="X8775930486BD0C5B" name="X8775930486BD0C5B"></a></p>
<h5>14.3-5 Gcdex</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Gcdex</code>( <var class="Arg">m</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a record <code class="code">g</code> describing the extended greatest common divisor of <var class="Arg">m</var> and <var class="Arg">n</var>. The component <code class="code">gcd</code> is this gcd, the components <code class="code">coeff1</code> and <code class="code">coeff2</code> are integer cofactors such that <code class="code">g.gcd = g.coeff1 * <var class="Arg">m</var> + g.coeff2 * <var class="Arg">n</var></code>, and the components <code class="code">coeff3</code> and <code class="code">coeff4</code> are integer cofactors such that <code class="code">0 = g.coeff3 * <var class="Arg">m</var> + g.coeff4 * <var class="Arg">n</var></code>.</p>
<p>If <var class="Arg">m</var> and <var class="Arg">n</var> both are nonzero, <code class="code">AbsInt( g.coeff1 )</code> is less than or equal to <code class="code">AbsInt(<var class="Arg">n</var>) / (2 * g.gcd)</code>, and <code class="code">AbsInt( g.coeff2 )</code> is less than or equal to <code class="code">AbsInt(<var class="Arg">m</var>) / (2 * g.gcd)</code>.</p>
<p>If <var class="Arg">m</var> or <var class="Arg">n</var> or both are zero <code class="code">coeff3</code> is <code class="code">-<var class="Arg">n</var> / g.gcd</code> and <code class="code">coeff4</code> is <code class="code"><var class="Arg">m</var> / g.gcd</code>.</p>
<p>The coefficients always form a unimodular matrix, i.e., the determinant <code class="code">g.coeff1 * g.coeff4 - g.coeff3 * g.coeff2</code> is <span class="SimpleMath">\(1\)</span> or <span class="SimpleMath">\(-1\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gcdex( 123, 66 );</span>
rec( coeff1 := 7, coeff2 := -13, coeff3 := -22, coeff4 := 41,
gcd := 3 )
</pre></div>
<p>This means <span class="SimpleMath">\(3 = 7 * 123 - 13 * 66\)</span>, <span class="SimpleMath">\(0 = -22 * 123 + 41 * 66\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gcdex( 0, -3 );</span>
rec( coeff1 := 0, coeff2 := -1, coeff3 := 1, coeff4 := 0, gcd := 3 )
<span class="GAPprompt">gap></span> <span class="GAPinput">Gcdex( 0, 0 );</span>
rec( coeff1 := 1, coeff2 := 0, coeff3 := 0, coeff4 := 1, gcd := 0 )
</pre></div>
<p><code class="func">GcdRepresentation</code> (<a href="chap56_mj.html#X7ABB91EF838075EF"><span class="RefLink">56.7-3</span></a>) provides similar functionality over arbitrary Euclidean rings.</p>
<p><a id="X7B33143E78A8DDE3" name="X7B33143E78A8DDE3"></a></p>
<h5>14.3-6 LcmInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LcmInt</code>( <var class="Arg">m</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the least common multiple of the integers <var class="Arg">m</var> and <var class="Arg">n</var>.</p>
<p><code class="func">LcmInt</code> is a method used by the general operation <code class="func">Lcm</code> (<a href="chap56_mj.html#X7ABA92057DD6C7AF"><span class="RefLink">56.7-6</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">LcmInt( 123, 66 );</span>
2706
</pre></div>
<p><a id="X79B466E984CD52D4" name="X79B466E984CD52D4"></a></p>
<h5>14.3-7 CoefficientsQadic</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CoefficientsQadic</code>( <var class="Arg">i</var>, <var class="Arg">q</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the <var class="Arg">q</var>-adic representation of the integer <var class="Arg">i</var> as a list <span class="SimpleMath">\(l\)</span> of coefficients satisfying the equality <span class="SimpleMath">\(\textit{i} = \sum_{{j = 0}} \textit{q}^j \cdot l[j+1]\)</span> for an integer <span class="SimpleMath">\(\textit{q} > 1\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:=CoefficientsQadic(462,3);</span>
[ 0, 1, 0, 2, 2, 1 ]
</pre></div>
<p><a id="X83124F86839DC7E6" name="X83124F86839DC7E6"></a></p>
<h5>14.3-8 CoefficientsMultiadic</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CoefficientsMultiadic</code>( <var class="Arg">ints</var>, <var class="Arg">int</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the multiadic expansion of the integer <var class="Arg">int</var> modulo the integers given in <var class="Arg">ints</var> (in ascending order). It returns a list of coefficients in the <em>reverse</em> order to that in <var class="Arg">ints</var>.</p>
<p><a id="X84A1900E82902B5F" name="X84A1900E82902B5F"></a></p>
<h5>14.3-9 ChineseRem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ChineseRem</code>( <var class="Arg">moduli</var>, <var class="Arg">residues</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">ChineseRem</code> returns the combination of the <var class="Arg">residues</var> modulo the <var class="Arg">moduli</var>, i.e., the unique integer <code class="code">c</code> from <code class="code">[0..Lcm(<var class="Arg">moduli</var>)-1]</code> such that <code class="code">c = <var class="Arg">residues</var>[i]</code> modulo <code class="code"><var class="Arg">moduli</var>[i]</code> for all <code class="code">i</code>, if it exists. If no such combination exists <code class="func">ChineseRem</code> signals an error.</p>
<p>Such a combination does exist if and only if <code class="code"><var class="Arg">residues</var>[i] = <var class="Arg">residues</var>[k] mod Gcd( <var class="Arg">moduli</var>[i], <var class="Arg">moduli</var>[k] )</code> for every pair <code class="code">i</code>, <code class="code">k</code>. Note that this implies that such a combination exists if the moduli are pairwise relatively prime. This is called the Chinese remainder theorem.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ChineseRem( [ 2, 3, 5, 7 ], [ 1, 2, 3, 4 ] );</span>
53
<span class="GAPprompt">gap></span> <span class="GAPinput">ChineseRem( [ 6, 10, 14 ], [ 1, 3, 5 ] );</span>
103
</pre></div>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ChineseRem( [ 6, 10, 14 ], [ 1, 2, 3 ] );</span>
Error, the residues must be equal modulo 2 called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
<span class="GAPbrkprompt">brk></span> <span class="GAPinput">gap></span>
</pre></div>
<p><a id="X7E404B1183DBC82A" name="X7E404B1183DBC82A"></a></p>
<h5>14.3-10 PowerModInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PowerModInt</code>( <var class="Arg">r</var>, <var class="Arg">e</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns <span class="SimpleMath">\(\textit{r}^{\textit{e}} \pmod{\textit{m}}\)</span> for integers <var class="Arg">r</var>, <var class="Arg">e</var> and <var class="Arg">m</var>.</p>
<p>Note that <code class="func">PowerModInt</code> can reduce intermediate results and thus will generally be faster than using <var class="Arg">r</var><code class="code">^</code><var class="Arg">e</var><code class="code"> mod </code><var class="Arg">m</var>, which would compute <span class="SimpleMath">\(\textit{r}^{\textit{e}}\)</span> first and reduces the result afterwards.</p>
<p><code class="func">PowerModInt</code> is a method for the general operation <code class="func">PowerMod</code> (<a href="chap56_mj.html#X805A35D684B7A952"><span class="RefLink">56.7-9</span></a>).</p>
<p><a id="X82005E587F0CB02A" name="X82005E587F0CB02A"></a></p>
<h4>14.4 <span class="Heading">Prime Integers and Factorization</span></h4>
<p><a id="X86F5E4CD82FEB9F4" name="X86F5E4CD82FEB9F4"></a></p>
<h5>14.4-1 Primes</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Primes</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p><code class="func">Primes</code> is a strictly sorted list of the 168 primes less than 1000.</p>
<p>This is used in <code class="func">IsPrimeInt</code> (<a href="chap14_mj.html#X78FDA4437EDCA70C"><span class="RefLink">14.4-2</span></a>) and <code class="func">FactorsInt</code> (<a href="chap14_mj.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>) to cast out small primes quickly.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Primes[1];</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">Primes[100];</span>
541
</pre></div>
<p><a id="X78FDA4437EDCA70C" name="X78FDA4437EDCA70C"></a></p>
<h5>14.4-2 IsPrimeInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPrimeInt</code>( <var class="Arg">n</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">‣ IsProbablyPrimeInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IsPrimeInt</code> returns <code class="keyw">false</code> if it can prove that the integer <var class="Arg">n</var> is composite and <code class="keyw">true</code> otherwise. By convention <code class="code">IsPrimeInt(0) = IsPrimeInt(1) = false</code> and we define <code class="code">IsPrimeInt(-</code><var class="Arg">n</var><code class="code">) = IsPrimeInt(</code><var class="Arg">n</var><code class="code">)</code>.</p>
<p><code class="func">IsPrimeInt</code> will return <code class="keyw">true</code> for every prime <var class="Arg">n</var>. <code class="func">IsPrimeInt</code> will return <code class="keyw">false</code> for all composite <var class="Arg">n</var> <span class="SimpleMath">\(< 10^{18}\)</span> and for all composite <var class="Arg">n</var> that have a factor <span class="SimpleMath">\(p < 1000\)</span>. So for integers <var class="Arg">n</var> <span class="SimpleMath">\(< 10^{18}\)</span>, <code class="func">IsPrimeInt</code> is a proper primality test. It is conceivable that <code class="func">IsPrimeInt</code> may return <code class="keyw">true</code> for some composite <var class="Arg">n</var> <span class="SimpleMath">\(> 10^{18}\)</span>, but no such <var class="Arg">n</var> is currently known. So for integers <var class="Arg">n</var> <span class="SimpleMath">\(> 10^{18}\)</span>, <code class="func">IsPrimeInt</code> is a probable-primality test. <code class="func">IsPrimeInt</code> will issue a warning when its argument is probably prime but not a proven prime. (The function <code class="func">IsProbablyPrimeInt</code> will do a similar calculation but not issue a warning.) The warning can be switched off by <code class="code">SetInfoLevel( InfoPrimeInt, 0 );</code>, the default level is <span class="SimpleMath">\(1\)</span> (also see <code class="func">SetInfoLevel</code> (<a href="chap7_mj.html#X7A43B9E68765EE9E"><span class="RefLink">7.4-3</span></a>) ).</p>
<p>If composites that fool <code class="func">IsPrimeInt</code> do exist, they would be extremely rare, and finding one by pure chance might be less likely than finding a bug in <strong class="pkg">GAP</strong>. We would appreciate being informed about any example of a composite number <var class="Arg">n</var> for which <code class="func">IsPrimeInt</code> returns <code class="keyw">true</code>.</p>
<p><code class="func">IsPrimeInt</code> is a deterministic algorithm, i.e., the computations involve no random numbers, and repeated calls will always return the same result. <code class="func">IsPrimeInt</code> first does trial divisions by the primes less than 1000. Then it tests that <var class="Arg">n</var> is a strong pseudoprime w.r.t. the base 2. Finally it tests whether <var class="Arg">n</var> is a Lucas pseudoprime w.r.t. the smallest quadratic nonresidue of <var class="Arg">n</var>. A better description can be found in the comment in the library file <code class="file">primality.gi</code>.</p>
<p>The time taken by <code class="func">IsPrimeInt</code> is approximately proportional to the third power of the number of digits of <var class="Arg">n</var>. Testing numbers with several hundreds digits is quite feasible.</p>
<p><code class="func">IsPrimeInt</code> is a method for the general operation <code class="func">IsPrime</code> (<a href="chap56_mj.html#X7AA107AE7F79C6D8"><span class="RefLink">56.5-8</span></a>).</p>
<p>Remark: In future versions of <strong class="pkg">GAP</strong> we hope to change the definition of <code class="func">IsPrimeInt</code> to return <code class="keyw">true</code> only for proven primes (currently, we lack a sufficiently good primality proving function). In applications, use explicitly <code class="func">IsPrimeInt</code> or <code class="func">IsProbablyPrimeInt</code> with this change in mind.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimeInt( 2^31 - 1 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimeInt( 10^42 + 1 );</span>
false
</pre></div>
<p><a id="X7CD977B17B4A7A4B" name="X7CD977B17B4A7A4B"></a></p>
<h5>14.4-3 PrimalityProof</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrimalityProof</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Construct a machine verifiable proof of the primality of (the probable prime) <var class="Arg">n</var>, following the ideas of <a href="chapBib_mj.html#biBBLS1975">[BLS75]</a>. The proof consists of various Fermat and Lucas pseudoprimality tests, which taken as a whole prove the primality. The proof is represented as a list of witnesses of two kinds. The first kind, <code class="code">[ "F", divisor, base ]</code>, indicates a successful Fermat pseudoprimality test, where <var class="Arg">n</var> is a strong pseudoprime at <code class="keyw">base</code> with order not divisible by <span class="SimpleMath">\((\textit{n}-1)/divisor\)</span>. The second kind, <code class="code">[ "L", divisor, discriminant, P ]</code> indicates a successful Lucas pseudoprimality test, for a quadratic form of given <code class="keyw">discriminant</code> and middle term <code class="keyw">P</code> with an extra check at <span class="SimpleMath">\((\textit{n}+1)/divisor\)</span>.</p>
<p><a id="X8443125D7FD6F2A6" name="X8443125D7FD6F2A6"></a></p>
<h5>14.4-4 IsPrimePowerInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPrimePowerInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IsPrimePowerInt</code> returns <code class="keyw">true</code> if the integer <var class="Arg">n</var> is a prime power and <code class="keyw">false</code> otherwise.</p>
<p>An integer <span class="SimpleMath">\(n\)</span> is a <em>prime power</em> if there exists a prime <span class="SimpleMath">\(p\)</span> and a positive integer <span class="SimpleMath">\(i\)</span> such that <span class="SimpleMath">\(p^i = n\)</span>. If <span class="SimpleMath">\(n\)</span> is negative the condition is that there must exist a negative prime <span class="SimpleMath">\(p\)</span> and an odd positive integer <span class="SimpleMath">\(i\)</span> such that <span class="SimpleMath">\(p^i = n\)</span>. The integers 1 and -1 are not prime powers.</p>
<p>Note that <code class="func">IsPrimePowerInt</code> uses <code class="func">SmallestRootInt</code> (<a href="chap14_mj.html#X7F98A0CE7B9FD366"><span class="RefLink">14.2-10</span></a>) and a probable-primality test (see <code class="func">IsPrimeInt</code> (<a href="chap14_mj.html#X78FDA4437EDCA70C"><span class="RefLink">14.4-2</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimePowerInt( 31^5 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimePowerInt( 2^31-1 ); # 2^31-1 is actually a prime</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimePowerInt( 2^63-1 );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered( [-10..10], IsPrimePowerInt );</span>
[ -8, -7, -5, -3, -2, 2, 3, 4, 5, 7, 8, 9 ]
</pre></div>
<p><a id="X78744C367A94C69F" name="X78744C367A94C69F"></a></p>
<h5>14.4-5 NextPrimeInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NextPrimeInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">NextPrimeInt</code> returns the smallest prime which is strictly larger than the integer <var class="Arg">n</var>.</p>
<p>Note that <code class="func">NextPrimeInt</code> uses a probable-primality test (see <code class="func">IsPrimeInt</code> (<a href="chap14_mj.html#X78FDA4437EDCA70C"><span class="RefLink">14.4-2</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NextPrimeInt( 541 ); NextPrimeInt( -1 );</span>
547
2
</pre></div>
<p><a id="X819060E17E83728A" name="X819060E17E83728A"></a></p>
<h5>14.4-6 PrevPrimeInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrevPrimeInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">PrevPrimeInt</code> returns the largest prime which is strictly smaller than the integer <var class="Arg">n</var>.</p>
<p>Note that <code class="func">PrevPrimeInt</code> uses a probable-primality test (see <code class="func">IsPrimeInt</code> (<a href="chap14_mj.html#X78FDA4437EDCA70C"><span class="RefLink">14.4-2</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrevPrimeInt( 541 ); PrevPrimeInt( 1 );</span>
523
-2
</pre></div>
<p><a id="X82C989DB84744B36" name="X82C989DB84744B36"></a></p>
<h5>14.4-7 FactorsInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorsInt</code>( <var class="Arg">n</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">‣ FactorsInt</code>( <var class="Arg">n:</var> <var class="Arg">RhoTrials</var> <var class="Arg">:=</var> <var class="Arg">trials</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">FactorsInt</code> returns a list of factors of a given integer <var class="Arg">n</var> such that <code class="code">Product( FactorsInt( <var class="Arg">n</var> ) ) = <var class="Arg">n</var></code>. If <span class="SimpleMath">\(|n| \leq 1\)</span> the list <code class="code">[<var class="Arg">n</var>]</code> is returned. Otherwise the result contains probable primes, sorted by absolute value. The entries will all be positive except for the first one in case of a negative <var class="Arg">n</var>.</p>
<p>See <code class="func">PrimeDivisors</code> (<a href="chap14_mj.html#X80E7A5D381C64CC9"><span class="RefLink">14.4-8</span></a>) for a function that returns a set of (probable) primes dividing <var class="Arg">n</var>.</p>
<p>Note that <code class="func">FactorsInt</code> uses a probable-primality test (see <code class="func">IsPrimeInt</code> (<a href="chap14_mj.html#X78FDA4437EDCA70C"><span class="RefLink">14.4-2</span></a>)). Thus <code class="func">FactorsInt</code> might return a list which contains composite integers. In such a case you will get a warning about the use of a probable prime. You can switch off these warnings by <code class="code">SetInfoLevel( InfoPrimeInt, 0 );</code> (also see <code class="func">SetInfoLevel</code> (<a href="chap7_mj.html#X7A43B9E68765EE9E"><span class="RefLink">7.4-3</span></a>)).</p>
<p>The time taken by <code class="func">FactorsInt</code> is approximately proportional to the square root of the second largest prime factor of <var class="Arg">n</var>, which is the last one that <code class="func">FactorsInt</code> has to find, since the largest factor is simply what remains when all others have been removed. Thus the time is roughly bounded by the fourth root of <var class="Arg">n</var>. <code class="func">FactorsInt</code> is guaranteed to find all factors less than <span class="SimpleMath">\(10^6\)</span> and will find most factors less than <span class="SimpleMath">\(10^{10}\)</span>. If <var class="Arg">n</var> contains multiple factors larger than that <code class="func">FactorsInt</code> may not be able to factor <var class="Arg">n</var> and will then signal an error.</p>
<p><code class="func">FactorsInt</code> is used in a method for the general operation <code class="func">Factors</code> (<a href="chap56_mj.html#X82D6EDC685D12AE2"><span class="RefLink">56.5-9</span></a>).</p>
<p>In the second form, <code class="func">FactorsInt</code> calls <code class="code">FactorsRho</code> with a limit of <var class="Arg">trials</var> on the number of trials it performs. The default is 8192. Note that Pollard's Rho is the fastest method for finding prime factors with roughly 5-10 decimal digits, but becomes more and more inferior to other factorization techniques like e.g. the Elliptic Curves Method (ECM) the bigger the prime factors are. Therefore instead of performing a huge number of Rho trials, it is usually more advisable to install the FactInt package and then simply to use the operation Factors (56.5-9). The factorization of the 8-th Fermat number by Pollard's Rho below takes already a while.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FactorsInt( -Factorial(6) );</span>
[ -2, 2, 2, 2, 3, 3, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Set( FactorsInt( Factorial(13)/11 ) );</span>
[ 2, 3, 5, 7, 13 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">FactorsInt( 2^63 - 1 );</span>
[ 7, 7, 73, 127, 337, 92737, 649657 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">FactorsInt( 10^42 + 1 );</span>
[ 29, 101, 281, 9901, 226549, 121499449, 4458192223320340849 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">FactorsInt(2^256+1:RhoTrials:=100000000);</span>
[ 1238926361552897,
93461639715357977769163558199606896584051237541638188580280321 ]
</pre></div>
<p><a id="X80E7A5D381C64CC9" name="X80E7A5D381C64CC9"></a></p>
<h5>14.4-8 PrimeDivisors</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrimeDivisors</code>( <var class="Arg">n</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">PrimeDivisors</code> returns for a non-zero integer <var class="Arg">n</var> a set of its positive (probable) primes divisors. In rare cases the result could contain a composite number which passed certain primality tests, see <code class="func">IsProbablyPrimeInt</code> (<a href="chap14_mj.html#X78FDA4437EDCA70C"><span class="RefLink">14.4-2</span></a>) and <code class="func">FactorsInt</code> (<a href="chap14_mj.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>) for more details.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrimeDivisors(-12);</span>
[ 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">PrimeDivisors(1);</span>
[ ]
</pre></div>
<p><a id="X786FF92C7C54BF97" name="X786FF92C7C54BF97"></a></p>
<h5>14.4-9 PartialFactorization</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PartialFactorization</code>( <var class="Arg">n</var>[, <var class="Arg">effort</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">PartialFactorization</code> returns a partial factorization of the integer <var class="Arg">n</var>. No assertions are made about the primality of the factors, except of those mentioned below.</p>
<p>The argument <var class="Arg">effort</var>, if given, specifies how intensively the function should try to determine factors of <var class="Arg">n</var>. The default is <var class="Arg">effort</var> = 5.</p>
<ul>
<li><p>If <var class="Arg">effort</var> = 0, trial division by the primes below 100 is done. Returned factors below <span class="SimpleMath">\(10^4\)</span> are guaranteed to be prime.</p>
</li>
<li><p>If <var class="Arg">effort</var> = 1, trial division by the primes below 1000 is done. Returned factors below <span class="SimpleMath">\(10^6\)</span> are guaranteed to be prime.</p>
</li>
<li><p>If <var class="Arg">effort</var> = 2, additionally trial division by the numbers in the lists <code class="code">Primes2</code> and <code class="code">ProbablePrimes2</code> is done, and perfect powers are detected. Returned factors below <span class="SimpleMath">\(10^6\)</span> are guaranteed to be prime.</p>
</li>
<li><p>If <var class="Arg">effort</var> = 3, additionally <code class="code">FactorsRho</code> (Pollard's Rho) with RhoTrials = 256 is used.
</li>
<li><p>If <var class="Arg">effort</var> = 4, as above, but <code class="code">RhoTrials</code> = 2048.</p>
</li>
<li><p>If <var class="Arg">effort</var> = 5, as above, but <code class="code">RhoTrials</code> = 8192. Returned factors below <span class="SimpleMath">\(10^{12}\)</span> are guaranteed to be prime, and all prime factors below <span class="SimpleMath">\(10^6\)</span> are guaranteed to be found.</p> | | |
