Changed layout for more manageable volumes

1 files changed, 0 insertions, 1542 deletions

diff --git a/3.2.1.2.lyx b/3.2.1.2.lyx
deleted file mode 100644
index ad58b78..0000000
--- a/3.2.1.2.lyx
+++ /dev/null
@@ -1,1542 +0,0 @@
-#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