#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