

%% LyX 2.1.4 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[12pt,english,hebrew]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{fontspec}
\setmainfont[Mapping=tex-text]{David CLM}
\setsansfont[Mapping=tex-text]{Hadasim CLM}
\usepackage{fancyhdr}
\pagestyle{fancy}
\usepackage{pifont}
\usepackage{url}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}
\newtheorem{thm}{\protect\theoremname}[section]
  \theoremstyle{definition}
  \newtheorem{defn}[thm]{\protect\definitionname}
  \theoremstyle{remark}
  \newtheorem{note}[thm]{\protect\notename}
  \theoremstyle{remark}
  \newtheorem{claim}[thm]{\protect\claimname}
  \theoremstyle{definition}
  \newtheorem{example}[thm]{\protect\examplename}
  \theoremstyle{definition}
  \newtheorem{xca}[thm]{\protect\exercisename}
\theoremstyle{remark}
\newtheorem*{solution*}{פתרון}
  \theoremstyle{plain}
  \newtheorem{question}[thm]{\protect\questionname}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{tikz}
\usepackage{mathdots}

\setmonofont[Script=Hebrew]{Miriam Mono CLM}
\newfontfamily{\englishfont}[Ligatures=TeX]{TeX Gyre Pagella}
%\newfontfamily{\englishfont}[Ligatures=TeX]{Latin Modern Roman}

\fancyhf{} % sets both header and footer to nothing
\renewcommand{\headrulewidth}{0pt}
\fancyfoot[C]{\textup{\thepage}}

\renewcommand*{\refname}{Bibliography}

\theoremstyle{definition}
\newtheorem{quesh}[thm]{שאלה}
\renewenvironment{question}{\begin{quesh}}{\end{quesh}}

%LyX does not like Longrightarrow in hebrew... replace by hack
%\mathrel{=}\joinrel\Rightarrow

\AtBeginDocument{
  \def\labelitemi{\Pisymbol{psy}{183}}
}

\makeatother

\usepackage{xunicode}
\usepackage{polyglossia}
\setdefaultlanguage{hebrew}
\setotherlanguage{english}
  \addto\captionsenglish{\renewcommand{\claimname}{Claim}}
  \addto\captionsenglish{\renewcommand{\definitionname}{Definition}}
  \addto\captionsenglish{\renewcommand{\examplename}{Example}}
  \addto\captionsenglish{\renewcommand{\exercisename}{Exercise}}
  \addto\captionsenglish{\renewcommand{\notename}{Note}}
  \addto\captionsenglish{\renewcommand{\questionname}{Question}}
  \addto\captionsenglish{\renewcommand{\remarkname}{Remark}}
  \addto\captionsenglish{\renewcommand{\theoremname}{Theorem}}
  \addto\captionshebrew{\renewcommand{\claimname}{טענה}}
  \addto\captionshebrew{\renewcommand{\definitionname}{הגדרה}}
  \addto\captionshebrew{\renewcommand{\examplename}{דוגמה}}
  \addto\captionshebrew{\renewcommand{\exercisename}{תרגיל}}
  \addto\captionshebrew{\renewcommand{\notename}{הערה}}
  \addto\captionshebrew{\renewcommand{\questionname}{שאלה}}
  \addto\captionshebrew{\renewcommand{\remarkname}{הערה}}
  \addto\captionshebrew{\renewcommand{\theoremname}{משפט}}
  \providecommand{\claimname}{טענה}
  \providecommand{\definitionname}{הגדרה}
  \providecommand{\examplename}{דוגמה}
  \providecommand{\exercisename}{תרגיל}
  \providecommand{\notename}{הערה}
  \providecommand{\questionname}{שאלה}
  \providecommand{\remarkname}{הערה}
\providecommand{\theoremname}{משפט}

\begin{document}
\makeatletter
\renewcommand{\SepMark}[1]{\def\@SepMark{#1}}
\makeatother
\SepMark{.}
\global\long\def\lcm{\operatorname{lcm}}



\title{מערך תרגיל קורס {\beginL 89-214\endL} סמסטר א' תשע\char`\"{}ו\\
מבנים אלגבריים למדעי המחשב}


\date{ספטמבר {\beginL 2015\endL}, גרסה {\beginL 0.1\endL}}

\maketitle
\thispagestyle{fancy} %% Bug of first page numbering is wrong font.


\section*{מבוא}

נתחיל עם כמה דגשים:
\begin{itemize}
\item דף הקורס נמצא באתר \textenglish{\url{www.math-wiki.com}}.
\item שאלות בנוגע לחומר הלימודי מומלץ לשאול בדף השיחה באתר של הקורס.
\item ישנה חובת הגשת תרגילים, אבל בודקים רק לחצי מהסטודנטים (ואולי יהיו
בחנים שיתבססו על התרגילים).
\item נשמח לכל הערה על מסמך זה.
\end{itemize}

\section{מבוא לתורת המספרים}

נסמן כמה קבוצות של מספרים:
\begin{itemize}
\item $\mathbb{N}=\left\{ 1,2,3,\dots\right\} $ המספרים הטבעיים.
\item $\mathbb{Z}=\left\{ 0,\pm1,\pm2,\pm3,\dots\right\} $ המספרים השלמים\textenglish{,}
מגרמנית: \textenglish{Zahlen}.
\item $\mathbb{Q}=\left\{ \frac{p}{q}:p\in\mathbb{Z},q\in\mathbb{Z}\backslash\left\{ 0\right\} \right\} $
המספרים הרציונליים.
\item $\mathbb{R}$ המספרים הממשיים.
\item $\mathbb{C}$ המספרים המרוכבים.
\end{itemize}
מתקיים $\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}$.

יהי $n$ מספר טבעי. נסמן את הכפולות שלו ב-$n\mathbb{Z}=\left\{ 0,\pm n,\pm2n,\dots\right\} $.
\begin{defn}
יהיו $a,b$ מספרים שלמים. נאמר כי \emph{$a$ מחלק את $b$} אם קיים
$k\in\mathbb{Z}$ כך ש-$ka=b$, ונסמן $a|b$. למשל $-5|10$.\end{defn}
\begin{thm}[משפט החילוק, או חלוקה אוקלידית]
לכל $d\ne0,n\in\mathbb{Z}$ קיימים $q,r$ יחידים כך ש-$n=qd+r$ וגם
$0\le r<\left|d\right|$.
\end{thm}
המשפט לעיל מתאר \char`\"{}מה קורה\char`\"{} כאשר מחלקים את $n$ ב-$d$.
הבחירה בשמות הפרמטרים במשפט מגיעה מלע\char`\"{}ז (מאנגלית?) \textenglish{quotient}
(מנה) ו-\textenglish{remainder} (שארית).
\begin{defn}
בהנתן שני מספרים שלמים $n,m$ \emph{המחלק המשותף המירבי} (ממ\char`\"{}מ,
\textenglish{greatest common divisor}) שלהם מוגדר להיות המספר
\[
\gcd(n,m)=\max\left\{ d\in\mathbb{N}:d|n\wedge d|m\right\}
\]
לעיתים נסמן $\left(n,m\right)$. למשל $\left(6,10\right)=2$. נאמר
כי $n,m$ \emph{זרים} אם $\left(n,m\right)=1$. למשל $\left(2,5\right)=1$.\end{defn}
\begin{note}
אם $d|a$ וגם $d|b$, אזי $d$ מחלק כל צירוף לינארי של $a$ ו-$b$.\end{note}
\begin{claim}
\label{claim:gcd-n-m-gcd-m-r}אם $n=qm+r$, אז $\left(n,m\right)=\left(m,r\right)$.\end{claim}
\begin{proof}
נסמן $d=(n,m)$, וצ\char`\"{}ל כי $d=\left(m,r\right)$. אנו יודעים
כי $d|n$ וגם $d|m$. אנו יכולים להציג את $r$ כצירוף לינארי של $n,m$,
ולכן $d|r=n-qm$. מכך קיבלנו $d\le(m,r)$.\\
כעת, לפי הגדרה $(m,r)|r$ וגם $(m,r)|m$, ולכן $(m,r)|n$ כי $n$
הוא צירוף לינארי של $m,r$. אם ידוע כי $(m,r)|m$ וגם $(m,r)|n$,
אזי $(m,r)\le d$. סך הכל קיבלנו כי $d=(m,r)$.\end{proof}
\begin{thm}[אלגוריתם אוקלידס]
\char`\"{}המתכון\char`\"{} למציאת ממ\char`\"{}מ בעזרת שימוש חוזר
בטענה \ref{claim:gcd-n-m-gcd-m-r} הוא אלגוריתם אוקלידס. ניתן להניח
$0\le m<n$. אם $m=0$, אזי $\left(n,m\right)=n$. אחרת נכתוב $n=qm+r$
כאשר $0\le r<m$ ונמשיך עם $\left(n,m\right)=\left(m,r\right)$. (הבינו
למה האלגוריתם חייב להעצר.)\end{thm}
\begin{example}
נחשב את הממ\char`\"{}מ של $53$ ו-$47$ בעזרת אלגוריתם אוקלידס
\begin{align*}
\left(53,47\right) & =\left[53=1\cdot47+6\right]\\
\left(47,6\right) & =\left[47=7\cdot6+5\right]\\
\left(6,5\right) & =1
\end{align*}


דוגמה נוספת עבור מספרים שאינם זרים:
\begin{align*}
\left(224,63\right) & =\left[224=3\cdot63+35\right]\\
\left(63,35\right) & =\left[63=1\cdot35+28\right]\\
\left(35,28\right) & =\left[35=1\cdot28+7\right]\\
\left(28,7\right) & =\left[28=4\cdot7+0\right]\\
\left(7,0\right) & =7
\end{align*}
\end{example}
\begin{thm}[אפיון הממ\char`\"{}מ כצירוף לינארי מזערי]
מתקיים לכל מספרים שלמים $a,b$ כי
\[
\left(a,b\right)=\min_{u,v}\left\{ au+bv\in\mathbb{N}\right\}
\]
בפרט קיימים $s,t\in\mathbb{Z}$ כך ש-$\left(a,b\right)=sa+tb$.\end{thm}
\begin{note}
מן המשפט קיבלנו כי $\left(a,b\right)\in a\mathbb{Z}+b\mathbb{Z}$.\end{note}
\begin{example}
כדי למצוא את המקדמים $s,t$ כשמביעים את הממ\char`\"{}מ כצירוף לינארי
כנ\char`\"{}ל נשתמש ב\emph{אלגוריתם אוקלידס המוכלל}:
\begin{align*}
\left(234,61\right) & =\left[{\scriptstyle 234=3\cdot61+51}\Rightarrow51=234-3\cdot61\right]\\
\left(61,51\right) & =\left[{\scriptstyle 61=1\cdot51+10}\Rightarrow10=61-1\cdot51=61-1\cdot(234-3\cdot61)=-1\cdot234+4\cdot61\right]\\
\left(51,10\right) & =\left[{\scriptstyle 51=5\cdot10+1}\Rightarrow1=51-5\cdot10=51-5\cdot(-1\cdot234+4\cdot61)=6\cdot234-23\cdot61\right]\\
\left(10,1\right) & =1
\end{align*}
ולכן $\left(234,61\right)=1=6\cdot234-23\cdot61$.\end{example}
\begin{xca}
יהיו $a,b,c$ מספרים שלמים כך ש-$\left(a,b\right)=1$ וגם $a|bc$.
הראו כי $a|c$.\end{xca}
\begin{solution*}
לפי אפיון הממ\char`\"{}מ כצירוף לינארי, קיימים $s,t$ כך ש-$1=sa+tb$.
נכפיל ב-$c$ ונקבל $c=sac+tbc$. ברור כי $a|sac$ ולפי הנתון גם $a|tbc$.
לכן $a|\left(sac+tbc\right)$, כלומר $a|c$.\end{solution*}
\begin{claim}
תכונות של ממ\char`\"{}מ:
\begin{enumerate}
\item יהי $d=(n,m)$ ויהי $e$ כך ש-$e|m$ וגם $e|n$, אזי $e|d$.
\item $(an,am)=a(n,m)$
\item אם $p$ ראשוני וגם $p|ab$, אזי $p|a$ או $p|b$.
\end{enumerate}
\end{claim}
\begin{proof}[הוכחת התכונות]

\begin{enumerate}
\item קיימים $s,t$ כך ש-$d=sn+tm$. כיוון ש-$e|n,m$, אז הוא מחלק גם את
צירוף לינארי שלהם $sn+tm$, ז\char`\"{}א את $d$.
\item (חלק מתרגיל הבית)
\item אם $p\nmid a$, אז $(p,a)=1$. לכן קיימים $s,t$ כך ש-$sa+tp=1$.
נכפיל את השיוויון האחרון ב-$b$ ונקבל $sab+tpb=b$. ברור כי $p$ מחלק
את אגף שמאל (הרי $p|ab$), ולכן $p$ מחלק את אגף ימין, כלומר $p|b$.
\end{enumerate}
\end{proof}
\begin{defn}
בהנתן שני מספרים שלמים $n,m$ \emph{הכפולה המשותפת המזערית} (כמ\char`\"{}מ,
\textenglish{least common multiple}) שלהם מוגדרת להיות
\[
\lcm(n,m)=\min\left\{ d\in\mathbb{N}:n|d\wedge m|d\right\}
\]
לעיתים נסמן $\left[n,m\right]$. למשל $\left[6,10\right]=30$ו-$\left[2,5\right]=10$.\end{defn}
\begin{claim}
תכונות של כמ\char`\"{}מ:
\begin{enumerate}
\item אם $m|a$ וגם $n|a$, אז $\left[n,m\right]|a$.
\item $\left[n,m\right]\left(n,m\right)=\left|nm\right|$. למשל $\left[6,4\right]\left(6,4\right)=12\cdot2=24=6\cdot4$.
\end{enumerate}
\end{claim}
\begin{proof}[הוכחת התכונות]

\begin{enumerate}
\item יהיו $q,r$ כך ש-$a=q\left[n,m\right]+r$ כאשר $0\le r<\left[n,m\right]$.
מהנתון כי $n,m|a$ ולפי הגדרה $n,m|\left[n,m\right]$, נובע כי $n,m|r$.
אם $r\ne0$ זו סתירה למינימליות של $\left[n,m\right]$. לכן $a=q\left[n,m\right]$,
כלומר $\left[n,m\right]|a$.
\item נראה דרך קלה לחישוב הממ\char`\"{}מ והכמ\char`\"{}מ בעזרת הפירוק של
מספר למכפלת גורמים ראשוניים. נניח כי הפירוק הוא
\begin{align*}
n & =\prod_{i=1}^{\infty}p_{i}^{\beta_{i}}=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}p_{3}^{\beta_{3}}\dots &  & m=\prod_{i=1}^{\infty}p_{i}^{\alpha_{i}}=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}p_{3}^{\alpha_{3}}\dots
\end{align*}
כאשר $\alpha_{i},\beta_{i}\ge0$ (והם כמעט תמיד אפס כי המכפלה סופית).
כעת צריך להשתכנע כי
\begin{align*}
\left(n,m\right) & =\prod_{i=1}^{\infty}p_{i}^{\min(\alpha_{i},\beta_{i})} &  & \left[n,m\right]=\prod_{i=1}^{\infty}p_{i}^{\max(\alpha_{i},\beta_{i})}
\end{align*}
ומפני שלכל שני מספרים $\alpha,\beta$ מתקיים $\alpha+\beta=\min(\alpha,\beta)+\max(\alpha,\beta)$,
אז $\left[n,m\right]\left(n,m\right)=\left|nm\right|$.
\end{enumerate}
\end{proof}
\begin{question}[לבית]
אפשר להגדיר ממ\char`\"{}מ ליותר מזוג מספרים. יהי $d$ הממ\char`\"{}מ
של המספרים $n_{1},\dots,n_{k}$. הראו שקיימים מספרים שלמים $s_{1},\dots,s_{k}$
המקיימים $s_{1}n_{1}+\dots+s_{k}n_{k}=d$. רמז: אינדוקציה על $k$.\end{question}
\begin{defn}
יהי $n$ מספר טבעי. נאמר כי $a,b\in\mathbb{Z}$ הם \emph{שקולים בשארית
חלוקה ב-$n$} אם $n|a-b$. כלומר קיים $k\in\mathbb{Z}$ כך ש-$a=b+kn$.
נסמן זאת $a\equiv b\pmod n$ ונקרא זאת \char`\"{}$a$ שקול ל-$b$
מודולו $n$\char`\"{}.\end{defn}
\begin{claim}
שקילות מודולו $n$ היא יחס שקילות. כפל וחיבור מודולו $n$ מוגדרים
היטב. כלומר אם $a\equiv b,c\equiv d\pmod n$, אז $ac\equiv bd\pmod n$
וגם $a+c\equiv b+d\pmod n$.\end{claim}
\begin{xca}
מצאו את הספרה האחרונה של $333^{333}$.\end{xca}
\begin{solution*}
נשים לב כי $333^{333}=3^{333}\cdot111^{333}$. לכן
\begin{align*}
111 & \equiv1\pmod{10}\Rightarrow111^{333}\equiv1^{333}\equiv1\pmod{10}\\
3^{333} & =3^{4\cdot83+1}=\left(3^{4}\right)^{81}\cdot3=81^{83}\cdot3\equiv1^{83}\cdot3\pmod{10}\\
333^{333} & =3^{333}\cdot111^{333}\equiv3\pmod{10}
\end{align*}
ומכאן שהספרה האחרונה היא $3$.\end{solution*}
\begin{xca}[אם יש זמן]
מצאו $0\le x\in\mathbb{Z}$ כך ש-$61x\equiv1\pmod{234}$.\end{xca}
\begin{solution*}
לפי הנתון, קיים $k\in\mathbb{Z}$ כך ש-$61x+234k\equiv1$. ז\char`\"{}א
$1$ הוא צירוף לינארי (מינימלי במקרה זה) של $61$ ו-$234$. לפי איפיון
ממ\char`\"{}מ קיבלנו כי $\left(234,61\right)=1$. כלומר $k,x$ הם
המקדמים מן המשפט של איפיון הממ\char`\"{}מ כצירוף לינארי מזערי. לפי
תרגיל קודם $1=6\cdot234-23\cdot61$. לכן $x\equiv-23\pmod{234}$,
וכדי להבטיח כי $x$ אינו שלילי נבחר $x=211$.\end{solution*}
\begin{thm}[משפט השאריות הסיני]
אם $n,m$ זרים, אזי לכל $a,b\in\mathbb{Z}$ קיים $x$ יחיד עד כדי
שקילות מודולו $nm$ כך ש-$x\equiv a\pmod n$, $x\equiv b\pmod m$
(יחד!).\end{thm}
\begin{proof}[הוכחה לא מלאה (בהרצאה?)]
מפני ש-$\left(n,m\right)=1$, אזי קיימים $s,t\in\mathbb{Z}$ כך ש-$sn+tm=1$.
כדי להוכיח קיום של $x$ כמו במשפט נתבונן ב-$bsn+atm$. מתקיים
\begin{align*}
bsn+atm & \equiv atm\equiv a\cdot1\equiv a\pmod n\\
bsn+atm & \equiv bsn\equiv b\cdot1\equiv b\pmod m
\end{align*}
ולכן $x=bsn+atm$ הוא פתרון אפשרי. ברור כי גם $x'=x+kmn$ לכל $k\in\mathbb{Z}$
הוא פתרון תקף.

כדי להראות יחידות של $x$ מודולו $nm$ נשתמש בטיעון קומבינטורי. לכל
זוג $\left(a,b\right)$ יש $x$ (לפחות אחד) המתאים לו מודולו $nm$.
ישנם בסה\char`\"{}כ $nm$ זוגות שונים $\left(a,b\right)$ (מודולו
$nm$), וכן רק $nm$ ערכים אפשריים ל-$x$ (מודולו $nm$). ההתאמה הזו
היא פונקציה חח\char`\"{}ע בין קבוצות סופיות שוות עוצמה, ולכן ההתאמה
היא גם על.\end{proof}
\begin{example}
נמצא $x\in\mathbb{Z}$ כך ש-$x\equiv1\pmod3$ וגם $x\equiv2\pmod5$.
ידוע כי $\left(5,3\right)=1$, ולכן $-1\cdot5+2\cdot3=1$. במקרה זה
$n=5,m=3$ וכן $s=-1,t=2$, ולפי משפט השאריות הסיני אפשר לבחור את
$x=1\cdot(-5)+2\cdot6=7$. אכן מתקיים $7\equiv1\pmod3$ וגם $7\equiv2\pmod5$.

משפט השאריות הסיני הוא יותר כללי. הנה גרסה שלו למערכת משוואות של שקילות
מודולו:\end{example}
\begin{thm}
תהא $\left\{ m_{1},\dots,m_{k}\right\} $ קבוצת מספרים טבעיים הזרים
זה לזה (כלומר כל זוג מספרים בקבוצה הוא זר). נסמן את מכפלתם ב-$m$.
בהנתן קבוצה כלשהי של שאריות $\left\{ a_{i}\left(\bmod{m_{i}}\right):1\le i\le k\right\} $,
קיימת שארית יחידה $x$ מודולו $m$ המהווה פתרון למערכת המשוואות
\[
\begin{cases}
x\equiv a_{1}\pmod{m_{1}}\\
\hphantom{x}\vdots\\
x\equiv a_{k}\pmod{m_{k}}
\end{cases}
\]
\end{thm}
\begin{example}
נמצא $y\in\mathbb{Z}$ כך ש-ש-$y\equiv1\pmod3$, $y\equiv2\pmod5$
וגם $y\equiv3\pmod7$. נשים לב שהפתרון $y=7$ מן הדוגמה הקודמת הוא
נכון כדי כדי הוספה של $3\cdot5=15$ (כי $15\equiv0\pmod3$ וגם $15\equiv0\pmod5$).
לכן את שתי המשוואות $y\equiv1\pmod3$, $y\equiv2\pmod5$ ניתן להחליף
במשוואה אחת $y\equiv7\pmod{15}$. נשים לב כי $\left(15,7\right)=1$
ולכן אפשר להשתמש במשפט השאריות הסיני בגרסה לזוג משוואות. בדקו כי $y=52$
מהווה פתרון.\end{example}

\end{document}


