Changed layout for more manageable volumes

1 files changed, 1542 insertions, 0 deletions

diff --git a/vol2/3.2.1.2.lyx b/vol2/3.2.1.2.lyx
new file mode 100644
index 0000000..ad58b78
--- /dev/null
+++ b/vol2/3.2.1.2.lyx
@@ -0,0 +1,1542 @@
+#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
+exerc1[10]
+\end_layout
+
+\end_inset
+
+What is the length of the period of the linear congruential sequence with 
+\begin_inset Formula $X_{0}=5772156648$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a=3141592621$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c=2718281829$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $m=10000000000$
+\end_inset
+
+?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Obviously 
+\begin_inset Formula $c$
+\end_inset
+
+ is relatively prime to 
+\begin_inset Formula $m$
+\end_inset
+
+.
+ Furthermore,
+ the prime divisors of 
+\begin_inset Formula $m$
+\end_inset
+
+ are 2 and 5 and 
+\begin_inset Formula $a-1$
+\end_inset
+
+ is a multiple of both 4 and 5.
+ Therefore the length is 
+\begin_inset Formula $m$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc2[10]
+\end_layout
+
+\end_inset
+
+Are the following two conditions sufficient to guarantee the maximum length period,
+ when 
+\begin_inset Formula $m$
+\end_inset
+
+ is a power of 2?
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $c$
+\end_inset
+
+ is odd;
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $a\bmod4=1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Yes,
+ by theorem A.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc6[20]
+\end_layout
+
+\end_inset
+
+Find all multipliers 
+\begin_inset Formula $a$
+\end_inset
+
+ that satisfy the conditions of Theorem A when 
+\begin_inset Formula $m=10^{6}-1$
+\end_inset
+
+.
+ (See Table 3.2.1.1–1.)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+By the table,
+ 
+\begin_inset Formula $m=3^{3}\cdot7\cdot11\cdot13\cdot37$
+\end_inset
+
+.
+ Multipliers are numbers 
+\begin_inset Formula $a$
+\end_inset
+
+ such that 
+\begin_inset Formula 
+\[
+a\bmod3=a\bmod7=a\bmod11=a\bmod13=a\bmod37=1.
+\]
+
+\end_inset
+
+These identities tell us that 
+\begin_inset Formula $a\equiv1\pmod{3\cdot7\cdot11\cdot13\cdot37=m/3^{2}=111111}$
+\end_inset
+
+,
+ so the possible values are 
+\begin_inset Formula $1,111112,222223,333334,444445,555556,666667,777778,888889$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc7[M23]
+\end_layout
+
+\end_inset
+
+The period of a congruential sequence need not start with 
+\begin_inset Formula $X_{0}$
+\end_inset
+
+,
+ but we can always find indices 
+\begin_inset Formula $\mu\geq0$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda>0$
+\end_inset
+
+ such that 
+\begin_inset Formula $X_{n+\lambda}=X_{n}$
+\end_inset
+
+ whenever 
+\begin_inset Formula $n\geq\mu$
+\end_inset
+
+,
+ and for which 
+\begin_inset Formula $\mu$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ are the smallest possible values with this property.
+ (See exercises 3.1–6 and 3.2.1–1.) If 
+\begin_inset Formula $\mu_{j}$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda_{j}$
+\end_inset
+
+ are the indices corresponding to the sequences
+\begin_inset Formula 
+\[
+(X_{0}\bmod p_{j}^{e_{j}},a\bmod p_{j}^{e_{j}},c\bmod p_{j}^{e_{j}},p_{j}^{e_{j}}),
+\]
+
+\end_inset
+
+and if 
+\begin_inset Formula $\mu$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ correspond to the composite sequence 
+\begin_inset Formula $(X_{0},a,c,p_{1}^{e_{1}}\cdots p_{t}^{e_{t}})$
+\end_inset
+
+,
+ Lemma Q states that 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ is the least common multiple of 
+\begin_inset Formula $\lambda_{1},\dots,\lambda_{t}$
+\end_inset
+
+.
+ What is the value of 
+\begin_inset Formula $\mu$
+\end_inset
+
+ in terms of the values of 
+\begin_inset Formula $\mu_{1},\dots,\mu_{t}$
+\end_inset
+
+?
+ What is the maximum possible value of 
+\begin_inset Formula $\mu$
+\end_inset
+
+ obtainable by varying 
+\begin_inset Formula $X_{0}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $c$
+\end_inset
+
+,
+ when 
+\begin_inset Formula $m=p_{1}^{e_{1}}\cdots p_{t}^{e_{t}}$
+\end_inset
+
+ is fixed?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Since the 
+\begin_inset Formula $j$
+\end_inset
+
+th sequence has values 
+\begin_inset Formula $X_{n}\bmod p_{j}^{e_{j}}$
+\end_inset
+
+,
+ and the 
+\begin_inset Formula $X_{n}$
+\end_inset
+
+ are uniquely determined by such values for all 
+\begin_inset Formula $j$
+\end_inset
+
+,
+ 
+\begin_inset Formula $(X_{n})_{n}$
+\end_inset
+
+ enters into a loop whenever all the 
+\begin_inset Formula $X_{n}\bmod p_{j}^{e_{j}}$
+\end_inset
+
+ have entered into a loop,
+ that is,
+ 
+\begin_inset Formula $\mu=\max_{j}\mu_{j}$
+\end_inset
+
+.
+ We are left to see what is the maximum 
+\begin_inset Formula $\mu$
+\end_inset
+
+ when 
+\begin_inset Formula $m=p^{e}$
+\end_inset
+
+ for some prime number 
+\begin_inset Formula $p$
+\end_inset
+
+ and positive integer 
+\begin_inset Formula $e$
+\end_inset
+
+ (for 
+\begin_inset Formula $m=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\mu=0$
+\end_inset
+
+).
+ In this case,
+ 
+\begin_inset Formula $\mu$
+\end_inset
+
+ is the lowest number such that
+\begin_inset Formula 
+\[
+X_{\mu}=X_{\mu+\lambda}\equiv X_{\mu}a^{\lambda}+\frac{a^{\lambda}-1}{a-1}c\pmod{p^{e}},
+\]
+
+\end_inset
+
+if and only if 
+\begin_inset Formula $X_{\mu}(1-a^{\lambda})\equiv\frac{a^{\lambda}-1}{a-1}c\pmod{p^{e}}$
+\end_inset
+
+,
+ so for 
+\begin_inset Formula $\mu>0$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\mu-1$
+\end_inset
+
+ must be a number such that
+\begin_inset Formula 
+\begin{align*}
+X_{\mu-1}(1-a^{\lambda}) & \not\equiv\frac{a^{\lambda}-1}{a-1}c, & aX_{\mu-1}(1-a^{\lambda}) & \equiv a\frac{a^{\lambda}-1}{a-1}c &  & \pmod{p^{e}},
+\end{align*}
+
+\end_inset
+
+where the first equation comes from changing 
+\begin_inset Formula $\mu$
+\end_inset
+
+ to 
+\begin_inset Formula $\mu-1$
+\end_inset
+
+ above and the second one from changing 
+\begin_inset Formula $X_{\mu}$
+\end_inset
+
+ to 
+\begin_inset Formula $aX_{\mu-1}+c$
+\end_inset
+
+ and rearranging terms.
+ This means that 
+\begin_inset Formula $a$
+\end_inset
+
+ must be a multiple of 
+\begin_inset Formula $p$
+\end_inset
+
+.
+ Then,
+\begin_inset Formula 
+\begin{align*}
+X_{e} & \equiv X_{0}a^{e}+\frac{a^{e}-1}{a-1}c\equiv(a^{e-1}+a^{e-2}+\dots+a+1)c, & \pmod{p^{e}},\\
+X_{e+\lambda} & \equiv X_{0}a^{e+\lambda}+\frac{a^{e+\lambda}-1}{a-1}c\equiv(a^{e-1}+a^{e-2}+\dots+a+1)c, & \pmod{p^{e}},
+\end{align*}
+
+\end_inset
+
+since 
+\begin_inset Formula $a^{e}\equiv0$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $\mu\leq e$
+\end_inset
+
+.
+ The value 
+\begin_inset Formula $\mu=e$
+\end_inset
+
+ is reached when 
+\begin_inset Formula $(X_{0},a,c)=(1,p,0)$
+\end_inset
+
+.
+ Summing up,
+ the maximum for 
+\begin_inset Formula $m=p_{1}^{e_{1}}\cdots p_{t}^{e_{t}}$
+\end_inset
+
+ is 
+\begin_inset Formula $\max\{e_{1},\dots,e_{t}\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc9[M22]
+\end_layout
+
+\end_inset
+
+(W.
+ E.
+ Thompson.) When 
+\begin_inset Formula $c=0$
+\end_inset
+
+ and 
+\begin_inset Formula $m=2^{e}\geq16$
+\end_inset
+
+,
+ Theorems B and C say that the period has length 
+\begin_inset Formula $2^{e-2}$
+\end_inset
+
+ if and only if the multiplier 
+\begin_inset Formula $a$
+\end_inset
+
+ satisfies 
+\begin_inset Formula $a\bmod8=3$
+\end_inset
+
+ or 
+\begin_inset Formula $a\bmod8=5$
+\end_inset
+
+.
+ Show that every such sequence is essentially a linear congruential sequence with 
+\begin_inset Formula $m=2^{e-2}$
+\end_inset
+
+,
+ having 
+\emph on
+full
+\emph default
+ period,
+ in the following sense:
+\end_layout
+
+\begin_layout Enumerate
+If 
+\begin_inset Formula $X_{n+1}=(4c+1)X_{n}\bmod2^{e}$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $X_{n}=4Y_{n}+1$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\[
+Y_{n+1}=((4c+1)Y_{n}+c)\bmod2^{e-2}.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+If 
+\begin_inset Formula $X_{n+1}=(4c-1)X_{n}\bmod2^{e}$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $X_{n}=((-1)^{n}(4Y_{n}+1))\bmod2^{e}$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\[
+Y_{n+1}=((1-4c)Y_{n}-c)\bmod2^{e-2}.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+We start with 
+\begin_inset Formula $(Y_{n})_{n}$
+\end_inset
+
+ as defined and see that 
+\begin_inset Formula $(X_{n})_{n}$
+\end_inset
+
+ calculated from there matches the initial definition of 
+\begin_inset Formula $(X_{n})_{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+We have 
+\begin_inset Formula $Y_{n}=\left((4c+1)^{n}Y_{0}+\frac{(4c+1)^{n}-1}{4\cancel{c}}\cancel{c}\right)\bmod2^{e-2}$
+\end_inset
+
+,
+ so
+\begin_inset Formula 
+\[
+4Y_{n}+1\equiv(4Y_{0}+1)(4c+1)^{n}\equiv(4c+1)^{n}X_{0}\equiv X_{n}\pmod{2^{e}}.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+We have 
+\begin_inset Formula $Y_{n}=\left((1-4c)^{n}Y_{0}-\frac{(1-4c)^{n}-1}{-4c}c\right)\bmod2^{e-2}$
+\end_inset
+
+,
+ so
+\begin_inset Formula 
+\begin{multline*}
+(-1)^{n}(4Y_{n}+1)\equiv(-1)^{n}\left(4(1-4c)^{n}Y_{0}+(1-4c)^{n}\right)=(4Y_{0}+1)(4c-1)^{n}=\\
+=(4c-1)^{n}X_{0}\equiv X_{n+1}\pmod{2^{e}}.
+\end{multline*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc16[M24]
+\end_layout
+
+\end_inset
+
+
+\emph on
+(Existence of primitive roots.)
+\emph default
+ Let 
+\begin_inset Formula $p$
+\end_inset
+
+ be a prime number.
+\end_layout
+
+\begin_layout Enumerate
+Consider the polynomial 
+\begin_inset Formula $f(x)=x^{n}+c_{1}x^{n-1}+\dots+c_{n}$
+\end_inset
+
+,
+ where the 
+\begin_inset Formula $c$
+\end_inset
+
+'s are integers.
+ Given that 
+\begin_inset Formula $a$
+\end_inset
+
+ is an integer for which 
+\begin_inset Formula $f(a)\equiv0\pmod p$
+\end_inset
+
+,
+ show that there exists a polynomial
+\begin_inset Formula 
+\[
+q(x)=x^{n-1}+q_{1}x^{n-2}+\dots+q_{n-1}
+\]
+
+\end_inset
+
+with integer coefficients such that 
+\begin_inset Formula $f(x)\equiv(x-a)q(x)\pmod p$
+\end_inset
+
+ for all integers 
+\begin_inset Formula $x$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Let 
+\begin_inset Formula $f(x)$
+\end_inset
+
+ be a polynomial as in (1).
+ Show that 
+\begin_inset Formula $f(x)$
+\end_inset
+
+ has at most 
+\begin_inset Formula $n$
+\end_inset
+
+ distinct 
+\begin_inset Quotes eld
+\end_inset
+
+roots
+\begin_inset Quotes erd
+\end_inset
+
+ modulo 
+\begin_inset Formula $p$
+\end_inset
+
+;
+ that is,
+ there are at most 
+\begin_inset Formula $n$
+\end_inset
+
+ integers 
+\begin_inset Formula $a$
+\end_inset
+
+,
+ with 
+\begin_inset Formula $0\leq a<p$
+\end_inset
+
+,
+ such that 
+\begin_inset Formula $f(a)\equiv0\pmod p$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Because of exercise 15(2),
+ the polynomial 
+\begin_inset Formula $f(x)=x^{\lambda(p)}-1$
+\end_inset
+
+ has 
+\begin_inset Formula $p-1$
+\end_inset
+
+ distinct roots;
+ hence there is an integer 
+\begin_inset Formula $a$
+\end_inset
+
+ with order 
+\begin_inset Formula $p-1$
+\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
+It suffices to prove that,
+ for 
+\begin_inset Formula $f\in\mathbb{Z}_{p}[X]$
+\end_inset
+
+ and 
+\begin_inset Formula $a\in\mathbb{Z}_{p}$
+\end_inset
+
+ with 
+\begin_inset Formula $f(a)=0$
+\end_inset
+
+,
+ there exists 
+\begin_inset Formula $q\in\mathbb{Z}_{p}[X]$
+\end_inset
+
+ such that 
+\begin_inset Formula $f(x)\equiv(x-a)q(x)$
+\end_inset
+
+,
+ since then,
+ for 
+\begin_inset Formula $f$
+\end_inset
+
+ to have degree 
+\begin_inset Formula $n$
+\end_inset
+
+ and leading coefficient 1,
+ 
+\begin_inset Formula $q$
+\end_inset
+
+ must have degree 
+\begin_inset Formula $n-1$
+\end_inset
+
+ and leading coefficient 
+\begin_inset Formula $q$
+\end_inset
+
+.
+ This is immediate for 
+\begin_inset Formula $f=0$
+\end_inset
+
+,
+ so we prove it by induction on the degree 
+\begin_inset Formula $n\geq0$
+\end_inset
+
+ of 
+\begin_inset Formula $f$
+\end_inset
+
+.
+ If 
+\begin_inset Formula $n=0$
+\end_inset
+
+,
+ 
+\begin_inset Formula $f(a)=c_{0}\neq0\#$
+\end_inset
+
+,
+ so this follows trivially.
+ If 
+\begin_inset Formula $n>0$
+\end_inset
+
+,
+ let 
+\begin_inset Formula $g(x)\coloneqq f(x)-c_{0}(x-a)x^{n-1}$
+\end_inset
+
+ is a polynomial of degree 
+\begin_inset Formula $n-1$
+\end_inset
+
+ such that 
+\begin_inset Formula $g(a)=f(a)=0$
+\end_inset
+
+,
+ so by induction there exists 
+\begin_inset Formula $r\in\mathbb{Z}_{p}(x)$
+\end_inset
+
+ with 
+\begin_inset Formula $g(x)=(x-a)r(x)$
+\end_inset
+
+.
+ But then 
+\begin_inset Formula $f(x)=g(x)+c_{0}(x-a)x^{n-1}=(x-a)(r(x)+c_{0}x^{n-1})$
+\end_inset
+
+.
+ Note that this proof is valid even when changing 
+\begin_inset Formula $\mathbb{Z}_{p}$
+\end_inset
+
+ to any other domain.
+\end_layout
+
+\begin_layout Enumerate
+If 
+\begin_inset Formula $a$
+\end_inset
+
+ and 
+\begin_inset Formula $b$
+\end_inset
+
+ are different roots of 
+\begin_inset Formula $f$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $f(x)=(x-a)q(x)$
+\end_inset
+
+ for some 
+\begin_inset Formula $q\in\mathbb{Z}_{p}[X]$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $b$
+\end_inset
+
+ is still a root of 
+\begin_inset Formula $q$
+\end_inset
+
+ as,
+ if it wasn't,
+ it wouldn't be a root of 
+\begin_inset Formula $f$
+\end_inset
+
+ either.
+ Therefore,
+ by induction,
+ a polynomial 
+\begin_inset Formula $f\in\mathbb{Z}_{p}[X]\setminus0$
+\end_inset
+
+ with 
+\begin_inset Formula $n$
+\end_inset
+
+ different roots has at least degree 
+\begin_inset Formula $n$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Yes.
+ Trivial.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc20[M24]
+\end_layout
+
+\end_inset
+
+(G.
+ Marsaglia.) The purpose of this exercise is to study the period length of an 
+\emph on
+arbitrary
+\emph default
+ linear congruential sequence.
+ Let 
+\begin_inset Formula $Y_{n}=1+a+\dots+a^{n-1}$
+\end_inset
+
+,
+ so that 
+\begin_inset Formula $X_{n}=(AY_{n}+X_{0})\bmod m$
+\end_inset
+
+ for some constant 
+\begin_inset Formula $A$
+\end_inset
+
+ by Eq.
+ 3.2.1–(8).
+\end_layout
+
+\begin_layout Enumerate
+Prove that the period length of 
+\begin_inset Formula $\langle X_{n}\rangle$
+\end_inset
+
+ is the period length of 
+\begin_inset Formula $\langle Y_{n}\bmod m'\rangle$
+\end_inset
+
+,
+ where 
+\begin_inset Formula $m'=m/\gcd(A,m)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Prove that the period length of 
+\begin_inset Formula $\langle Y_{n}\bmod p^{e}\rangle$
+\end_inset
+
+ satisfies the following when 
+\begin_inset Formula $p$
+\end_inset
+
+ is prime:
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+If 
+\begin_inset Formula $a\bmod p=0$
+\end_inset
+
+,
+ it is 1.
+\end_layout
+
+\begin_layout Enumerate
+If 
+\begin_inset Formula $a\bmod p=1$
+\end_inset
+
+,
+ it is 
+\begin_inset Formula $p^{e}$
+\end_inset
+
+,
+ except when 
+\begin_inset Formula $p=2$
+\end_inset
+
+ and 
+\begin_inset Formula $e\geq2$
+\end_inset
+
+ and 
+\begin_inset Formula $a\bmod4=3$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+If 
+\begin_inset Formula $p=2$
+\end_inset
+
+,
+ 
+\begin_inset Formula $e\geq2$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $a\bmod4=3$
+\end_inset
+
+,
+ it is twice the order of 
+\begin_inset Formula $a$
+\end_inset
+
+ modulo 
+\begin_inset Formula $p^{e}$
+\end_inset
+
+ (see exercise 11),
+ unless 
+\begin_inset Formula $a\equiv-1\pmod{2^{e}}$
+\end_inset
+
+ when it is 2.
+\end_layout
+
+\begin_layout Enumerate
+If 
+\begin_inset Formula $a\bmod p>1$
+\end_inset
+
+,
+ it is the order of 
+\begin_inset Formula $a$
+\end_inset
+
+ modulo 
+\begin_inset Formula $p^{e}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\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_{n}=X_{n+m}\iff AY_{n}\equiv AY_{n+m}\pmod m\iff Y_{n}\equiv Y_{n+m}\pmod{m'}.
+\]
+
+\end_inset
+
+Note that 
+\begin_inset Formula $\langle Y_{n}\bmod t\rangle$
+\end_inset
+
+,
+ 
+\begin_inset Formula $t\in\mathbb{Z}^{+}$
+\end_inset
+
+,
+ is the linear congruential sequence with 
+\begin_inset Formula $Y_{0}=0$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a=a$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $m=t$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+For 
+\begin_inset Formula $n\geq e-1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $Y_{n}=(1+a+a^{2}+\dots+a^{e-1})\bmod p$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Then we're in the conditions of Theorem A.
+\end_layout
+
+\begin_layout Enumerate
+If 
+\begin_inset Formula $e=2$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $a\equiv-1\pmod 4$
+\end_inset
+
+ and this part doesn't apply,
+ so we assume 
+\begin_inset Formula $e>2$
+\end_inset
+
+.
+ Let 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ be the order of 
+\begin_inset Formula $a$
+\end_inset
+
+ modulo 
+\begin_inset Formula $2^{e}$
+\end_inset
+
+,
+ obviously 
+\begin_inset Formula $\lambda>1$
+\end_inset
+
+,
+ so
+\begin_inset Formula 
+\begin{multline*}
+Y_{k}=1+a+\dots+a^{k-1}=\frac{a^{k}-1}{a-1}\equiv Y_{0}=0\pmod{2^{e}}\iff\\
+\iff a^{k}-1\equiv0\pmod{2^{e}(a-1)}\iff2^{e}(a-1)\mid a^{k}-1.
+\end{multline*}
+
+\end_inset
+
+The order 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ of 
+\begin_inset Formula $a$
+\end_inset
+
+ modulo 
+\begin_inset Formula $2^{e}$
+\end_inset
+
+ is the smallest number such that 
+\begin_inset Formula $2^{e}\mid a^{k}-1$
+\end_inset
+
+,
+ and in fact
+\begin_inset Formula 
+\[
+2^{e}\mid a^{k}-1\iff a^{k}\equiv1\pmod{2^{e}}\iff\lambda\mid k.
+\]
+
+\end_inset
+
+Exercise 11 gives us an unique 
+\begin_inset Formula $f>1$
+\end_inset
+
+ such that 
+\begin_inset Formula $a\bmod2^{f+1}=2^{f}\pm1$
+\end_inset
+
+,
+ and then says that 
+\begin_inset Formula $\lambda=2^{e-f}$
+\end_inset
+
+.
+ This can be used to prove that 
+\begin_inset Formula $a^{\lambda}-1$
+\end_inset
+
+ is not a multiple of 
+\begin_inset Formula $2^{e}(a-1)$
+\end_inset
+
+,
+ as if this were the case,
+ then 
+\begin_inset Formula $a^{\lambda-1}$
+\end_inset
+
+ would be a multiple of 
+\begin_inset Formula $2^{e+1}$
+\end_inset
+
+ because 
+\begin_inset Formula $a-1$
+\end_inset
+
+ is even,
+ but by Exercise 11 the order of 
+\begin_inset Formula $a$
+\end_inset
+
+ modulo 
+\begin_inset Formula $e+1$
+\end_inset
+
+ is 
+\begin_inset Formula $2^{e+1-f}>\lambda\#$
+\end_inset
+
+.
+ However,
+ since 
+\begin_inset Formula $a^{\lambda}-1$
+\end_inset
+
+ is a multiple of both 
+\begin_inset Formula $2^{e}$
+\end_inset
+
+ and 
+\begin_inset Formula $a^{\lambda}-1$
+\end_inset
+
+,
+ it is a multiple of 
+\begin_inset Formula $\text{lcm}\{2^{e},a^{\lambda}-1\}=\frac{2^{e}(a^{\lambda}-1)}{2}$
+\end_inset
+
+ and therefore 
+\begin_inset Formula $a^{2\lambda}-1=(a^{\lambda}-1)(a^{\lambda}+1)=(a^{\lambda}-1)^{2}+2(a^{\lambda}-1)$
+\end_inset
+
+ is a multiple of 
+\begin_inset Formula $2^{e}(a^{\lambda}-1)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Like before,
+ 
+\begin_inset Formula $Y_{k}\equiv0\pmod{2^{e}}\iff p^{e}(a-1)\mid a^{k}-1$
+\end_inset
+
+.
+ This time,
+ however,
+ 
+\begin_inset Formula $\gcd\{a-1,p^{e}\}=1$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $p^{e}(a-1)\mid a^{k}-1\iff p^{e},a-1\mid a^{k}-1\iff p^{e}\mid a^{k}-1$
+\end_inset
+
+,
+ and the lowest 
+\begin_inset Formula $k$
+\end_inset
+
+ for which this happens is precisely the order of 
+\begin_inset Formula $a$
+\end_inset
+
+ modulo 
+\begin_inset Formula $p^{e}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc22[M25]
+\end_layout
+
+\end_inset
+
+Discuss the problem of finding moduli 
+\begin_inset Formula $m=b^{k}\pm b^{l}\pm1$
+\end_inset
+
+ so that the subtract-with-borrow and add-with-carry generators of exercise 3.2.1.1–14 will have very long periods.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+First we would need the prime factorization of 
+\begin_inset Formula $m$
+\end_inset
+
+,
+ which is not easily characterized from 
+\begin_inset Formula $b$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $l$
+\end_inset
+
+.
+ Once we have that we may apply Theorems A–C.
+ The solution in the book suggests looking for 
+\begin_inset Formula $m$
+\end_inset
+
+ to be prime.
+\end_layout
+
+\end_body
+\end_document