path: root/vol2/4.3.2.lyx

#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 
\begin{multline*}
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{multline*}

\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