Algorithms (task9)
Forfatter:
Kamila
Sidst opdateret:
8 år siden
Licens:
Creative Commons CC BY 4.0
Resumé:
Module math
\begin
Opdag hvorfor 18 millioner mennesker verden rundt stoler på Overleaf med deres arbejde.
Module math
\begin
Opdag hvorfor 18 millioner mennesker verden rundt stoler på Overleaf med deres arbejde.
{}\documentclass{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{tikz}
\usepackage{amscd}
\usepackage[inline]{enumitem}
\usepackage{amsmath}
\usepackage{dsfont}
\usepackage{indentfirst}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{epigraph}
\renewcommand{\thesection}{\arabic{section}}
\renewcommand{\baselinestretch}{1.0}
\renewcommand\normalsize{\sloppypar}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9.1in}
\setlength{\oddsidemargin}{-0.3in}
\setlength{\textwidth}{7in}
\setlength{\parindent}{0ex}
\setlength{\parskip}{1ex}
\title{Домашнее задание на девятую неделю}
\author{Бельденова Камила, 675}
\begin{document}
\maketitle
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
1&2&3&4&5&6&7&$\Sigma$\\
\hline
&&&&&&&\\
\hline
\end{tabular}
\\\\
\begin{enumerate}
\item[\textbf{Задача 1.}] Покажите, как вычислить $a^{54}$ за $7$ умножений. Можно ли еще быстрее?\\
\\
$1)$ $a \cdot a = a^{2}$\\
$2)$ $a^{2} \cdot a^{2} = a^{4}$\\
$3)$ $a^{4} \cdot a^{4} = a^{8}$\\
$4)$ $a \cdot a^{8} = a^{9}$\\
$5)$ $a^{9} \cdot a^{9} = a^{18}$\\
$6)$ $a^{9} \cdot a^{18} = a^{27}$\\
$7)$ $a^{27} \cdot a^{27} = a^{54}$\\
Нет, быстрее нельзя.\\
Первым шагом так и останется $a \cdot a = a^{2}$. Пусть дальше мы получим $a^{3}=a \cdot a^{2}$. Посмотрим сможем ли мы за оставшиеся $4$ шага получить $a^{54}$:\\
$3)$ $a^{3} \cdot a^{3} = a^{6}$\\
$4)$ $a^{6} \cdot a^{6} = a^{12}$\\
$5)$ $a^{12} \cdot a^{12} = a^{24}$\\
$6)$ $a^{24} \cdot a^{24} = a^{48}$\\
$a^{54}$ не получили $\Rightarrow$ вторым шагом оставим операцию $a^{2} \cdot a^{2} = a^{4}$. Тогда после третьего шага можем получить $a^{5}=a \cdot a^{4}$, $a^{6}=a^{2} \cdot a^{4}$ или $a^{8}=a^{4} \cdot a^{4}$. В случае с $a^{5}$ максимум, что мы можем получить: $a^{40}$ ~---~ за оставшиеся $3$ шага. Если же на третьем шаге мы получим $a^{6}$, то на шестом максимум ~---~ $a^{48}$ $\Rightarrow$ третьим шагом оставим операцию $a^{4} \cdot a^{4} = a^{8}$. На четвертом шаге можем получить:~ $a^{9}$, $a^{10}$, $a^{12}$ и $a^{16}$. Рассуждая аналогично предыдущим шагам, придем к выводу, что рациональнее всего оставить операцию $a^{8} \cdot a^{8} = a^{16}$, чтобы добиться результата за наименьшее количество шагов. Аналогично рассуждаем и на пятом шаге, оставляя в алгоритме операцию $a^{16} \cdot a^{16} = a^{32}$. Заметим, что имея $a$, $a^{2}$, $a^{4}$, $a^{8}$, $a^{16}$ и $a^{32}$, одним умножением мы не сможем получить $a^{54}$. Т.~е. несмотря на то, что на каждом шаге мы оставляли максимальный результат, мы не смогли получить $a^{54}$ быстрее, чем за 7 шагов $\Rightarrow$ быстрее, чем за $7$ умножений вычислить нельзя.\\
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 2.}] Делится ли $4^{1356}-9^{4824}$ на $35$? Делится ли $5^{30000}-6^{123456}$ на $35$?
\begin{enumerate}
\item
По свойству мультипликативности функции Эйлера:\\
$\varphi{(35)}=\varphi{(5)} \cdot \varphi{(7)}=(5-1)\cdot (7-1)=24\\$
По теореме Эйлера:\\
$4^{\varphi{(35)}}=4^{24} \equiv 1\pmod{35}$\\
$4^{1356}=4^{1344+12}=4^{24 \cdot 56} \cdot 4^{12} \equiv 1^{56} \cdot 4^{12}=256^{3} \equiv 11^{3}=11 \cdot 121 \equiv 11 \cdot 16 = 176 \equiv 1 \pmod{35}$\\
$9^{4824}=9^{24 \cdot 201} \equiv 1^{201} \equiv 1 \pmod{35} $\\
$4^{1356}-9^{4824} \equiv 1-1 \pmod{35}=0\pmod{35} \Rightarrow$ да, делится.\\
\item
$\varphi{(31)}=\varphi{(30)}$, т.~к. $31$ ~---~ простое число. \\
По теореме Эйлера:\\
$5^{\varphi{(31)}}=5^{30} \equiv 1\pmod{31}$\\
$5^{30000}=5^{30 \cdot 1000} \equiv 1^{1000} \equiv 1 \pmod{31}$\\
$6^{123456}=6^{30 \cdot 4115 +6} \equiv 1^{4115} \cdot 6^{6} = 36^{3}\equiv 5^{3} =125 \equiv 1 \pmod{31} $\\
$5^{30000}-6^{123456} \equiv 1-1 \pmod{31}=0\pmod{31} \Rightarrow$ да, делится.\\
\end{enumerate}
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 3.}] Пусть $F_{k}$ ~---~ $k$-ое число Фибоначчи.Найдите результат работы Алгоритма Евклида на паре $(F;F_{k+1})$ . Найдите также число итераций
алгоритма.\\
$F_{0}=0, F_{1}=1, F_{k}=F_{k-1}+F_{k-2}, k\geq 2 , k \in \mathbb{Z} $\\
Euclid:\\
$gcd(F_{k};F_{k+1})=gcd(F_{k};F_{k+1}-F_{k})=gcd(F_{k-1};F_{k})$ ~---~это первый шаг\\
Вторым шагом будет: $gcd(F_{k-1};F_{k})=gcd(F_{k-1};F_{k}-F_{k-1})=gcd(F_{k-2};F_{k-1})$\\
Продолжая выполнять алгоритм $k$ шагов, придем к выводу:\\
$gcd(F_{k};F_{k+1})=gcd(F_{1};F_{2})=1$ $\Rightarrow$ числа $F_{k};F_{k+1} взаимно просты.$\\
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 4.}]Найдите обратные $20\pmod{79}$, $3\pmod{62}$.\\
\item $20a \equiv 1\pmod{79}$\\
Euclid:\\
\begin{center} $20~79$\\
$20~19$\\
$1~~19$\\
$1~~~0$\\
\end{center}
Extended Euclid:\\
$1=20-19=20-(79-3 \cdot 20)=20-79+3 \cdot 20=4 \cdot \underline{20}-1 \cdot \underline{79} $\\
$20 \cdot 4 \equiv 1\pmod{79}$.\\
Ответ: $4$ является обратным к $20$ по модулю $79$.\\
\item $3a \equiv 1\pmod{62}$\\
Euclid:\\
\begin{center} $3~62$\\
$3~~2$\\
$1~~2$\\
$1~~0$\\
\end{center}
Extended Euclid:\\
$1=3-2=3-(62-3 \cdot 20)=3-62+3 \cdot 20=21 \cdot \underline{3}-1 \cdot \underline{62} $\\
$3 \cdot 21\equiv 1\pmod{62}$.\\
Ответ: $21$ является обратным к $3$ по модулю $62$.\\
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 5.}] Найдите все решения уравнения $35x=10\pmod{50}$.\\
Euclid:\\
$50~~35$\\
$15~~35$\\
$15~~~5$\\
$0~~~~5$\\
$gcd(50;35)=5$\\
Разделим уравнение на $5$:\\
$7x=2\pmod{10}$\\
Подберем решение $x_{0}$:\\
$7 \cdot 6 =2\pmod{10}$ $\Rightarrow$ $x_{0}=6$\\
$x=x_{0}+i \cdot \frac{n}{d}=6+10i$\\
$i=0,\ldots , d-1=0, \ldots,4$\\
Ответ: $x_{1}=6$, $x_{2}=16$, $x_{3}=26$, $x_{4}=36$, $x_{5}=46$.\\
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 6.}] Найдите наименьшее натуральное число, имеющее остатки $2,3,1$ от деления на $5, 13, 7$ соответственно.\\
\begin{equation*}
\begin{cases}
a=2\pmod{5}\\
a=3\pmod{13}\\
a=1\pmod{7}\\
\end{cases}
\end{equation*}
$n_{1}=5~~~~m_{1}=91$\\
$n_{2}=13~~~m_{2}=35$\\
$n_{3}=7~~~~m_{3}=65$\\
\begin{enumerate}
\item $5x_{5}+91y_{5}=1$\\
Euclid:\\
$5~~91$\\
$5~~~1$\\
$0~~~1$\\
Extended Euclid:\\
$1=1 \cdot \underline{91}-\underline{5} \cdot 18$\\
\[
\boxed { $91$y_{5}$$=$91$} \qquad
\]
\item $13x_{13}+35y_{13}=1$\\
Euclid:\\
$13~~35$\\
$13~~~9$\\
$4~~~~9$\\
$4~~~~1$\\
$0~~~1$\\
Extended Euclid:\\
$1=9-2 \cdot 4= 35-2 \cdot 13-2 \cdot (13-9)= 35-2 \cdot 13-2 \cdot( 13-(35-2 \cdot 13))=35-4 \cdot 13 + 2\cdot 35 - 4 \cdot 13 = \underline{3} \cdot 35-\underline{8} \cdot 13$\\
\[
\boxed { $35$y_{13}$$=$105$} \qquad
\]
\item $7x_{7}+65y_{7}=1$\\
Euclid:\\
$7~~~65$\\
$7~~~~2$\\
$1~~~~2$\\
$1~~~0$\\
Extended Euclid:\\
$1=7-2 \cdot 3= 7-3 \cdot (65-7 \cdot 9)= 7-3 \cdot 65+7 \cdot 27= 28 \cdot \underline{7}- 3 \cdot \underline{65} $\\
\[
\boxed { $65$y_{13}$$=$-195$} \qquad
\]
$a=2 \cdot 91 +3 \cdot 105 -195=302$\\
Ответ: $302$.\\
\end{enumerate}
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 7.}] Докажите, что в поле $\mathbb{F}_p =\mathbb{Z}/(p)$ выполняется равенство $(a+b)^p = a^p+b^p$.\\
$(a+b)^p = a^p+b^p=a^p+C_p^1a^{p-1}b^1+\ldots+C_p^{p-1}ab^{p-1}+b^p$\\
\\
Запишем формулу для биномиального коэффициента:\\
\begin{center}
$C_p^k=\frac{p!}{k!(p-k)!}=\frac{1 \cdot \ldots \cdot p}{k!(p-k)!}$.\\
\end{center}
Из формулы видно, что числа вида $C_p^k$ ($k \notin {0,p}$) кратны $p$, а, значит, сравнимы с $0$ по модулю $p$, поэтому имеем:\\
\begin{center}
$(a+b)^p \stackrel{mod{p}}= a^p+b^p$\\
\end{center}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ч.~т.~д.
\end{enumerate}
\end{document}