Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/doc/ref/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 18.9.2025 mit Größe 106 kB image not shown  

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>

</li>
<li><p>If <var class="Arg">effort</var> = 6 and the package <strong class="pkg">FactInt</strong> is loaded, in addition to the above quite a number of special cases are handled.</p>

</li>
<li><p>If <var class="Arg">effort</var> = 7 and the package <strong class="pkg">FactInt</strong> is loaded, the only thing which is not attempted to obtain a full factorization into Baillie-Pomerance-Selfridge-Wagstaff pseudoprimes is the application of the MPQS to a remaining composite with more than 50 decimal digits.</p>

</li>
</ul>
<p>Increasing the value of the argument <var class="Arg">effort</var> by one usually results in an increase of the runtime requirements by a factor of (very roughly!) 3 to 10. (Also see <code class="func">CheapFactorsInt</code> (<a href="../../pkg/edim/doc/chap1_mj.html#X7BAB977C7EB05067"><span class="RefLink">EDIM: CheapFactorsInt</span></a>)).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([0..5],i->PartialFactorization(97^35-1,i));</span>
[ [ 2, 2, 2, 2, 2, 3, 11, 31, 43,
      2446338959059521520901826365168917110105972824229555319002965029 ],
  [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967,
      2529823122088440042297648774735177983563570655873376751812787 ],
  [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967,
      2529823122088440042297648774735177983563570655873376751812787 ],
  [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321,
      242549173950325921859769421435653153445616962914227 ],
  [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321, 687121,
      352993394104278463123335513593170858474150787 ],
  [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321, 687121,
      20241187, 504769301, 34549173843451574629911361501 ] ]
</pre></div>

<p><a id="X803D431087B6FF28" name="X803D431087B6FF28"></a></p>

<h5>14.4-10 PrintFactorsInt</h5>

--> --------------------

--> maximum size reached

--> --------------------

100%


¤ Dauer der Verarbeitung: 0.30 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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.