4.3.2--3: Modular Arithmetic & How Fast Can We Multiply?

1 files changed, 746 insertions, 0 deletions

diff --git a/vol2/4.3.2.lyx b/vol2/4.3.2.lyx
new file mode 100644
index 0000000..4a16c48
--- /dev/null
+++ b/vol2/4.3.2.lyx
@@ -0,0 +1,746 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 620
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input defs
+\end_preamble
+\use_default_options true
+\maintain_unincluded_children no
+\language english
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_formatted_ref 0
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\docbook_mathml_prefix 1
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc5[M23]
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+Suppose that the method of (13) is continued until no more 
+\begin_inset Formula $m_{j}$
+\end_inset
+
+ can be chosen.
+ Does this 
+\begin_inset Quotes eld
+\end_inset
+
+greedy
+\begin_inset Quotes erd
+\end_inset
+
+ method give the largest attainable value 
+\begin_inset Formula $m_{1}m_{2}\dots m_{r}$
+\end_inset
+
+ such that the 
+\begin_inset Formula $m_{j}$
+\end_inset
+
+ are odd positive integers less than 100 that are relatively prime in pairs?
+\end_layout
+
+\begin_layout Enumerate
+What is the largest possible 
+\begin_inset Formula $m_{1}m_{2}\dots m_{r}$
+\end_inset
+
+ when each residue 
+\begin_inset Formula $u_{j}$
+\end_inset
+
+ must fit in eight bits of memory?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+No;
+ if we substitute,
+ say,
+ 
+\begin_inset Formula $m_{3}=95$
+\end_inset
+
+ with 19 and 25,
+ which weren't chosen before because they have common factors with 
+\begin_inset Formula $m_{3}$
+\end_inset
+
+,
+ then we get a modulo that is 5 times as large.
+ No other number in the sequence has common factors with 19 and 25 since,
+ if they had,
+ they would also have common factors with 95.
+\end_layout
+
+\begin_layout Enumerate
+We need to have each prime number to the greatest power that is at most 
+\begin_inset Formula $2^{8}=256$
+\end_inset
+
+,
+ so
+\begin_inset Formula 
+\begin{multline*}
+2^{8}\cdot3^{5}\cdot5^{3}\cdot7^{2}\cdot11^{2}\cdot13^{2}\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot\dots\cdot251=\\
+=166744908068958426716590087517763853502703245089096518499\\
+55453691538889375930032935391666564679008085339616000.
+\end{multline*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc7[M21]
+\end_layout
+
+\end_inset
+
+Show that (24) can be rewritten as follows:
+\begin_inset Formula 
+\begin{align*}
+v_{1} & \gets u_{1}\bmod m_{1},\\
+v_{2} & \gets(u_{2}-v_{1})c_{12}\bmod m_{2},\\
+v_{3} & \gets(u_{3}-(v_{1}+m_{1}v_{2}))c_{13}c_{23}\bmod m_{3},\\
+\vdots\\
+v_{r} & \gets(u_{r}-(v_{1}+m_{1}(v_{2}+m_{2}(v_{3}+\dots+m_{r-2}v_{r-1})\dots)))c_{1r}\cdots c_{(r-1)r}\bmod m_{r}.
+\end{align*}
+
+\end_inset
+
+If the formulas are rewritten in this way,
+ we see that only 
+\begin_inset Formula $r-1$
+\end_inset
+
+ constants 
+\begin_inset Formula $C_{j}=c_{1j}\cdots c_{(j-1)j}\bmod m_{j}$
+\end_inset
+
+ are needed instead of 
+\begin_inset Formula $r(r-1)/2$
+\end_inset
+
+ constants 
+\begin_inset Formula $c_{ij}$
+\end_inset
+
+ as in (24).
+ Discuss the relative merits of this version of the formula compared to (24),
+ from the standpoint of computer calculation.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+After expanding some products,
+ the general formula in the exercise is
+\begin_inset Formula 
+\[
+v_{r}=(u_{r}-v_{1}-m_{1}v_{2}-m_{1}m_{2}v_{3}-\dots-m_{1}\cdots m_{r-2}v_{r-1})c_{1r}\cdots c_{(r-1)r}\bmod m_{r},
+\]
+
+\end_inset
+
+but for 
+\begin_inset Formula $1\leq k\leq r$
+\end_inset
+
+,
+ 
+\begin_inset Formula $m_{1}\cdots m_{k}c_{1r}\cdots c_{kr}\equiv1\pmod{m_{r}}$
+\end_inset
+
+,
+ so this is equivalent to
+\begin_inset Formula 
+\[
+v_{r}=u_{r}c_{1r}\cdots c_{(r-1)r}-v_{1}c_{1r}\cdots c_{(r-1)r}-v_{2}c_{2r}\cdots c_{(r-1)r}-v_{3}c_{3r}\cdots c_{(r-1)r}-\dots-v_{r-1}c_{(r-1)r}\bmod m_{r},
+\]
+
+\end_inset
+
+which is precisely the formula in (24) after expanding all the products.
+\end_layout
+
+\begin_layout Standard
+With these formulas,
+ to calculate 
+\begin_inset Formula $v_{k}$
+\end_inset
+
+,
+ we do 
+\begin_inset Formula $k-1$
+\end_inset
+
+ multiplications modulo 
+\begin_inset Formula $m_{k}$
+\end_inset
+
+ and 
+\begin_inset Formula $k-1$
+\end_inset
+
+ additions,
+ the same amount as with (24).
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc12[M10]
+\end_layout
+
+\end_inset
+
+Prove that,
+ if 
+\begin_inset Formula $0\leq u,v<m$
+\end_inset
+
+,
+ the modular addition of 
+\begin_inset Formula $u$
+\end_inset
+
+ and 
+\begin_inset Formula $v$
+\end_inset
+
+ causes overflow (lies outside the range allowed by the modular representation) if and only if the sum is less than 
+\begin_inset Formula $u$
+\end_inset
+
+.
+ (Thus the overflow detection problem is equivalent to the comparison problem.)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+In this case 
+\begin_inset Formula $u+v\geq m$
+\end_inset
+
+ but 
+\begin_inset Formula $u+v<u+m<2m$
+\end_inset
+
+ (since 
+\begin_inset Formula $u,v<m$
+\end_inset
+
+),
+ so 
+\begin_inset Formula $(u+v)\bmod m=u+v-m<u$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+If 
+\begin_inset Formula $u+v<m$
+\end_inset
+
+,
+ because 
+\begin_inset Formula $u+v\geq0$
+\end_inset
+
+,
+ we would have 
+\begin_inset Formula $(u+v)\bmod m=u+v\geq u\#$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc13[M25]
+\end_layout
+
+\end_inset
+
+(
+\emph on
+Automorphic numbers.
+\emph default
+) An 
+\begin_inset Formula $n$
+\end_inset
+
+-digit decimal number 
+\begin_inset Formula $x>1$
+\end_inset
+
+ is called an 
+\begin_inset Quotes eld
+\end_inset
+
+automorph
+\begin_inset Quotes erd
+\end_inset
+
+ by recreational mathematicians if the last 
+\begin_inset Formula $n$
+\end_inset
+
+ digits of 
+\begin_inset Formula $x^{2}$
+\end_inset
+
+ are equal to 
+\begin_inset Formula $x$
+\end_inset
+
+.
+ For example,
+ 9376 is a 4-digit automorph,
+ since 
+\begin_inset Formula $9376^{2}=87909376$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Prove that an 
+\begin_inset Formula $n$
+\end_inset
+
+-digit number 
+\begin_inset Formula $x>1$
+\end_inset
+
+ is an automorph if and only if 
+\begin_inset Formula $x\bmod5^{n}=0\text{ or }1$
+\end_inset
+
+ and 
+\begin_inset Formula $x\bmod2^{n}=1\text{ or 0}$
+\end_inset
+
+,
+ respectively.
+ (Thus,
+ if 
+\begin_inset Formula $m_{1}=2^{n}$
+\end_inset
+
+ and 
+\begin_inset Formula $m_{2}=5^{n}$
+\end_inset
+
+,
+ the only two 
+\begin_inset Formula $n$
+\end_inset
+
+-digit automorphs are the numbers 
+\begin_inset Formula $M_{1}$
+\end_inset
+
+ and 
+\begin_inset Formula $M_{2}$
+\end_inset
+
+ in (7).)
+\end_layout
+
+\begin_layout Enumerate
+Prove that if 
+\begin_inset Formula $x$
+\end_inset
+
+ is an 
+\begin_inset Formula $n$
+\end_inset
+
+-digit automorph,
+ then 
+\begin_inset Formula $(3x^{2}-2x^{3})\bmod10^{2n}$
+\end_inset
+
+ is a 
+\begin_inset Formula $2n$
+\end_inset
+
+-digit automorph.
+\end_layout
+
+\begin_layout Enumerate
+Given that 
+\begin_inset Formula $cx\equiv1\pmod y$
+\end_inset
+
+,
+ find a simple formula for a number 
+\begin_inset Formula $c'$
+\end_inset
+
+ depending on 
+\begin_inset Formula $c$
+\end_inset
+
+ and 
+\begin_inset Formula $x$
+\end_inset
+
+ but not on 
+\begin_inset Formula $y$
+\end_inset
+
+,
+ such that 
+\begin_inset Formula $c'x^{2}\equiv1\pmod{y^{2}}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $x$
+\end_inset
+
+ is an automorph if and only if 
+\begin_inset Formula $x^{2}\bmod10^{n}=x$
+\end_inset
+
+,
+ if and only if 
+\begin_inset Formula $x^{2}\bmod5^{n}=x$
+\end_inset
+
+ and 
+\begin_inset Formula $x^{2}\bmod2^{n}=x$
+\end_inset
+
+,
+ but 
+\begin_inset Formula $\mathbb{Z}_{5^{n}}$
+\end_inset
+
+ and 
+\begin_inset Formula $\mathbb{Z}_{2^{n}}$
+\end_inset
+
+ are fields,
+ so by cancellation,
+ 
+\begin_inset Formula $x^{2}=x$
+\end_inset
+
+ in 
+\begin_inset Formula $\mathbb{Z}_{5^{n}}$
+\end_inset
+
+ or 
+\begin_inset Formula $\mathbb{Z}_{2^{n}}$
+\end_inset
+
+ if and only if 
+\begin_inset Formula $x=1$
+\end_inset
+
+.
+ The cases where 
+\begin_inset Formula $x\bmod5^{n}=x\bmod2^{n}=0\text{ or }1$
+\end_inset
+
+ are excluded because they are precisely 
+\begin_inset Formula $x=0$
+\end_inset
+
+ and 
+\begin_inset Formula $x=1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Let 
+\begin_inset Formula $k=2\text{ or }5$
+\end_inset
+
+ and 
+\begin_inset Formula $a\in\mathbb{Z}$
+\end_inset
+
+,
+ if 
+\begin_inset Formula $x=ak^{n}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula 
+\[
+3x^{2}-2x^{3}\equiv0\pmod{k^{2n}},
+\]
+
+\end_inset
+
+whereas if 
+\begin_inset Formula $x=ak^{n}+1$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\[
+3x^{2}-2x^{3}\equiv6ak^{n}+3-6ak^{n}-2=1\pmod{k^{2n}},
+\]
+
+\end_inset
+
+so the values of 
+\begin_inset Formula $3x^{2}-2x^{3}$
+\end_inset
+
+ modulo 
+\begin_inset Formula $2^{2n}$
+\end_inset
+
+ and 
+\begin_inset Formula $5^{2n}$
+\end_inset
+
+ are the same as those of 
+\begin_inset Formula $x$
+\end_inset
+
+ if 
+\begin_inset Formula $x$
+\end_inset
+
+ is an automorph.
+\end_layout
+
+\begin_layout Enumerate
+Let 
+\begin_inset Formula $c'\coloneqq c^{2}(3-2cx)$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $c'x^{2}=c^{2}x^{2}(3-2cx)=3(cx)^{2}-2(cx)^{3}$
+\end_inset
+
+ and,
+ if 
+\begin_inset Formula $a\in\mathbb{Z}$
+\end_inset
+
+ is such that 
+\begin_inset Formula $cx=ay+1$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\[
+3(cx)^{2}-2(cx)^{3}\equiv6ay+3-6ay-2=1\pmod{y^{2}}.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document