<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Теория чисел — Sage Tutorial in Russian v5.9</title>
<link rel="stylesheet" href="_static/sage.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '',
VERSION: '5.9',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<script type="text/javascript" src="_static/translations.js"></script>
<link rel="shortcut icon" href="_static/favicon.ico"/>
<link rel="top" title="Sage Tutorial in Russian v5.9" href="index.html" />
<link rel="up" title="Тур по Sage" href="tour.html" />
<link rel="next" title="Немного высшей математики" href="tour_advanced.html" />
<link rel="prev" title="Конечные группы, Абелевы группы" href="tour_groups.html" />
<link rel="icon" href="_static/sageicon.png" type="image/x-icon" />
</head>
<body>
<div class="related">
<h3>Просмотр</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="Словарь-указатель"
accesskey="I">словарь</a></li>
<li class="right" >
<a href="py-modindex.html" title="Python Module Index"
>модули</a> |</li>
<li class="right" >
<a href="tour_advanced.html" title="Немного высшей математики"
accesskey="N">следующий</a> |</li>
<li class="right" >
<a href="tour_groups.html" title="Конечные группы, Абелевы группы"
accesskey="P">предыдущий</a> |</li>
<a href="../index.html"><img src="_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
<li><a href="index.html">Sage Tutorial in Russian v5.9</a> »</li>
<li><a href="tour.html" accesskey="U">Тур по Sage</a> »</li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="id1">
<h1>Теория чисел<a class="headerlink" href="#id1" title="Ссылка на этот заголовок">¶</a></h1>
<p>Sage имеет обширную функциональность в плане теории чисел. Например,
можно производить арифметические операции в <img class="math" src="_images/math/adcdc17e456d03d86077bbe5ce4eeeb4d64e82ef.png" alt="\ZZ/N\ZZ"/>:</p>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: R = IntegerModRing(97)</span>
<span class="go">sage: a = R(2) / R(3)</span>
<span class="go">sage: a</span>
<span class="go">33</span>
<span class="go">sage: a.rational_reconstruction()</span>
<span class="go">2/3</span>
<span class="go">sage: b = R(47)</span>
<span class="go">sage: b^20052005</span>
<span class="go">50</span>
<span class="go">sage: b.modulus()</span>
<span class="go">97</span>
<span class="go">sage: b.is_square()</span>
<span class="go">True</span>
</pre></div>
</div>
<p>Sage содержит стандартные функции теории чисел. Например,</p>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: gcd(515,2005)</span>
<span class="go">5</span>
<span class="go">sage: factor(2005)</span>
<span class="go">5 * 401</span>
<span class="go">sage: c = factorial(25); c</span>
<span class="go">15511210043330985984000000</span>
<span class="go">sage: [valuation(c,p) for p in prime_range(2,23)]</span>
<span class="go">[22, 10, 6, 3, 2, 1, 1, 1]</span>
<span class="go">sage: next_prime(2005)</span>
<span class="go">2011</span>
<span class="go">sage: previous_prime(2005)</span>
<span class="go">2003</span>
<span class="go">sage: divisors(28); sum(divisors(28)); 2*28</span>
<span class="go">[1, 2, 4, 7, 14, 28]</span>
<span class="go">56</span>
<span class="go">56</span>
</pre></div>
</div>
<p>Отлично!</p>
<p>Функция <tt class="docutils literal"><span class="pre">sigma(n,k)</span></tt> в Sage суммирует <img class="math" src="_images/math/8c325612684d41304b9751c175df7bcc0f61f64f.png" alt="k"/>-е степени делителей <tt class="docutils literal"><span class="pre">n</span></tt>:</p>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: sigma(28,0); sigma(28,1); sigma(28,2)</span>
<span class="go">6</span>
<span class="go">56</span>
<span class="go">1050</span>
</pre></div>
</div>
<p>Далее покажем алгоритм Эвклида, <img class="math" src="_images/math/2c175f60eecef1de7560c3bdea495d69f26f719d.png" alt="\phi"/>-функцию Эйлера и китайскую
теорему об остатках:</p>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: d,u,v = xgcd(12,15)</span>
<span class="go">sage: d == u*12 + v*15</span>
<span class="go">True</span>
<span class="go">sage: n = 2005</span>
<span class="go">sage: inverse_mod(3,n)</span>
<span class="go">1337</span>
<span class="go">sage: 3 * 1337</span>
<span class="go">4011</span>
<span class="go">sage: prime_divisors(n)</span>
<span class="go">[5, 401]</span>
<span class="go">sage: phi = n*prod([1 - 1/p for p in prime_divisors(n)]); phi</span>
<span class="go">1600</span>
<span class="go">sage: euler_phi(n)</span>
<span class="go">1600</span>
<span class="go">sage: prime_to_m_part(n, 5)</span>
<span class="go">401</span>
</pre></div>
</div>
<p>Уясним кое-что для <img class="math" src="_images/math/c5e6973e15885269ed8323265980c3aca91edbb2.png" alt="3n+1"/>.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: n = 2005</span>
<span class="go">sage: for i in range(1000):</span>
<span class="gp">... </span> <span class="n">n</span> <span class="o">=</span> <span class="mi">3</span><span class="o">*</span><span class="n">odd_part</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span>
<span class="gp">... </span> <span class="k">if</span> <span class="n">odd_part</span><span class="p">(</span><span class="n">n</span><span class="p">)</span><span class="o">==</span><span class="mi">1</span><span class="p">:</span>
<span class="gp">... </span> <span class="k">print</span> <span class="n">i</span>
<span class="gp">... </span> <span class="k">break</span>
<span class="go">38</span>
</pre></div>
</div>
<p>Китайская теорема об остатках:</p>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: x = crt(2, 1, 3, 5); x</span>
<span class="go">11</span>
<span class="go">sage: x % 3 # x mod 3 = 2</span>
<span class="go">2</span>
<span class="go">sage: x % 5 # x mod 5 = 1</span>
<span class="go">1</span>
<span class="go">sage: [binomial(13,m) for m in range(14)]</span>
<span class="go">[1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1]</span>
<span class="go">sage: [binomial(13,m)%2 for m in range(14)]</span>
<span class="go">[1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]</span>
<span class="go">sage: [kronecker(m,13) for m in range(1,13)]</span>
<span class="go">[1, -1, 1, 1, -1, -1, -1, -1, 1, 1, -1, 1]</span>
<span class="go">sage: n = 10000; sum([moebius(m) for m in range(1,n)])</span>
<span class="go">-23</span>
<span class="go">sage: Partitions(4).list()</span>
<span class="go">[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]</span>
</pre></div>
</div>
<div class="section" id="id2">
<h2><img class="math" src="_images/math/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png" alt="p"/>–адические числа<a class="headerlink" href="#id2" title="Ссылка на этот заголовок">¶</a></h2>
<p>Поле <img class="math" src="_images/math/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png" alt="p"/>-адических чисел реализовано в Sage. Обратите внимание:
как только поле <img class="math" src="_images/math/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png" alt="p"/>-адических чисел создано, его точность не
может быть изменена.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: K = Qp(11); K</span>
<span class="go">11-adic Field with capped relative precision 20</span>
<span class="go">sage: a = K(211/17); a</span>
<span class="go">4 + 4*11 + 11^2 + 7*11^3 + 9*11^5 + 5*11^6 + 4*11^7 + 8*11^8 + 7*11^9</span>
<span class="go"> + 9*11^10 + 3*11^11 + 10*11^12 + 11^13 + 5*11^14 + 6*11^15 + 2*11^16</span>
<span class="go"> + 3*11^17 + 11^18 + 7*11^19 + O(11^20)</span>
<span class="go">sage: b = K(3211/11^2); b</span>
<span class="go">10*11^-2 + 5*11^-1 + 4 + 2*11 + O(11^18)</span>
</pre></div>
</div>
<p>Большое количество методов встроено для класса NumberField.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: R.<x> = PolynomialRing(QQ)</span>
<span class="go">sage: K = NumberField(x^3 + x^2 - 2*x + 8, 'a')</span>
<span class="go">sage: K.integral_basis()</span>
<span class="go">[1, 1/2*a^2 + 1/2*a, a^2]</span>
</pre></div>
</div>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: K.galois_group(type="pari")</span>
<span class="go">Galois group PARI group [6, -1, 2, "S3"] of degree 3 of the Number Field</span>
<span class="go">in a with defining polynomial x^3 + x^2 - 2*x + 8</span>
</pre></div>
</div>
<div class="highlight-python"><div class="highlight"><pre><span class="go">sage: K.polynomial_quotient_ring()</span>
<span class="go">Univariate Quotient Polynomial Ring in a over Rational Field with modulus</span>
<span class="go">x^3 + x^2 - 2*x + 8</span>
<span class="go">sage: K.units()</span>
<span class="go">[3*a^2 + 13*a + 13]</span>
<span class="go">sage: K.discriminant()</span>
<span class="go">-503</span>
<span class="go">sage: K.class_group()</span>
<span class="go">Class group of order 1 of Number Field in a with</span>
<span class="go">defining polynomial x^3 + x^2 - 2*x + 8</span>
<span class="go">sage: K.class_number()</span>
<span class="go">1</span>
</pre></div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Содержание</a></h3>
<ul>
<li><a class="reference internal" href="#">Теория чисел</a><ul>
<li><a class="reference internal" href="#id2"><img class="math" src="_images/math/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png" alt="p"/>–адические числа</a></li>
</ul>
</li>
</ul>
<h4>Предыдущий раздел</h4>
<p class="topless"><a href="tour_groups.html"
title="предыдущая глава">Конечные группы, Абелевы группы</a></p>
<h4>Следующий раздел</h4>
<p class="topless"><a href="tour_advanced.html"
title="следующая глава">Немного высшей математики</a></p>
<h3>На этой странице</h3>
<ul class="this-page-menu">
<li><a href="_sources/tour_numtheory.txt"
rel="nofollow">Показать исходный текст</a></li>
</ul>
<div id="searchbox" style="display: none">
<h3>Быстрый поиск</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" size="18" />
<!-- The shading of the "Go" button should be consistent -->
<!-- with the colour of the header and footer. See the file -->
<!-- doc/common/themes/sage/theme.conf for colours used by -->
<!-- the Sage theme. -->
<input type="submit" style="background-color: #B8B9F6" value="Искать" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Введите слова для поиска или имя модуля, класса или функции.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Просмотр</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="Словарь-указатель"
>словарь</a></li>
<li class="right" >
<a href="py-modindex.html" title="Python Module Index"
>модули</a> |</li>
<li class="right" >
<a href="tour_advanced.html" title="Немного высшей математики"
>следующий</a> |</li>
<li class="right" >
<a href="tour_groups.html" title="Конечные группы, Абелевы группы"
>предыдущий</a> |</li>
<a href="../index.html"><img src="_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
<li><a href="index.html">Sage Tutorial in Russian v5.9</a> »</li>
<li><a href="tour.html" >Тур по Sage</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright 2005--2011, The Sage Development Team.
При создании использован <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.1.3.
</div>
<script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle. Putting this code at the end of the body
* enables the toggle for the live, static, and offline docs. Note:
* sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;
jq(document).ready(function () {
var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
bod = jq('div.bodywrapper');
bar = jq('div.sphinxsidebar');
tog = jq('<div class="sphinxsidebartoggle"></div>');
/* Delayed resize helper. Not perfect but good enough. */
resize = function () {
setTimeout(function () {
tog.height(bod.height());
}, 100);
};
jq(window).resize(function () {
resize();
});
/* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
wid_old = '230px';
wid_new = '5px';
tog.css('background-color', bg)
.css('border-width', '0px')
.css('border-right', wid_new + ' ridge ' + bg)
.css('cursor', 'pointer')
.css('position', 'absolute')
.css('left', '-' + wid_new)
.css('top', '0px')
.css('width', wid_new);
bod.css('position', 'relative');
bod.prepend(tog);
resize();
/* Cookie helpers. */
key = 'sphinxsidebar=';
set_state = function (s) {
var date = new Date();
/* Expiry in 7 days. */
date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
document.cookie = key + encodeURIComponent(s) + '; expires=' +
date.toUTCString() + '; path=/';
};
get_state = function () {
var i, c, crumbs = document.cookie.split(';');
for (i = 0; i < crumbs.length; i += 1) {
c = crumbs[i].replace(/^\s+/, '');
if (c.indexOf(key) === 0) {
return decodeURIComponent(c.substring(key.length, c.length));
}
}
return null;
};
/* Event handlers. */
tog.mouseover(function (ev) {
tog.css('border-right-color', fg);
}).mouseout(function (ev) {
tog.css('border-right-color', bg);
}).click(function (ev) {
if (bod.hasClass('wide')) {
bod.removeClass('wide');
bod.css('margin-left', wid_old);
bar.css('width', wid_old);
bar.show();
set_state('visible');
} else {
set_state('hidden');
bar.hide();
bar.css('width', '0px');
bod.css('margin-left', wid_new);
bod.addClass('wide');
}
resize();
});
/* Hide the normally visible sidebar? */
if (get_state() === 'hidden') {
tog.trigger('click');
} else {
set_state('visible');
}
});
</script>
</body>
</html>
