#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,v1$ \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