Mat 2AL Fællesøvelser Uge 5

TAL 6 nr 9

Lad n være produktet af de r parvis primiske hele tal $n_1,\ldots ,n_r$. Vælg hele tal x_i og y_i så $x_in_i+y_in_i^{\perp}=1$ hvor $n_i^{\perp}=\frac{n}{n_i}$. Dette er muligt fordi n_i og $n_i^{\perp}$ er primiske (TAL 3.7,3.10). Med $e_i=y_in_i^{\perp}$ gælder
   $$\begin{align}n_ie_i &\equiv 0 \bmod n \\ e_ie_j &\equiv 0 \bmod n, \quad i \neq j \\ e_1 + \cdots + e_r &\equiv 1 \bmod n \end{align}$$
Tallene $n_ie_i=y_in_in_i^{\perp}=y_in$, $e_ie_j=y_iy_jn_i^{\perp}n_j^{\perp} = y_iy_jn\frac{n}{n_in_j}$, $i \neq j$, og

$$x_1 \cdots x_rn = (1-e_1)\cdots (1-e_r) = 1- (e_1 + \cdots e_r) + (\text{sum af mulipla af $e_ie_j$\space med $i \neq j$ })$$

er nemlig alle multipla af n.

Ligning (1) fortæller at multiplikation med e_i er en veldefineret afbildning ${\mathbf Z}/n_i \to {\mathbf Z}/n$. Lad $\mbox{$\nabla\colon {\mathbf Z}/n_1 \times \cdots \times {\mathbf Z}/n_r\rightarrow {\mathbf Z}/n$ }, (x_1,\ldots ,x_r) \to e_1x_1+ \cdots +e_rx_r$ være summen af disse r afbildninger. Sammensætningen

$${\mathbf Z}/n \xrightarrow{\Delta} {\mathbf Z}/n_1 \times \cdots \times {\mathbf Z}/n_r \xrightarrow{\nabla} {\mathbf Z}/n$$ (1)

af $\nabla$ og diagonalafbildningen $\Delta(x)=(x,\ldots ,x)$ er identiteten ifølge (3). Da begge mængder i (4) har kardinalitet n, er $\Delta$ og $\nabla$ hinandens inverse.
[Ex: $x\equiv 2 \bmod 5,\quad x \equiv 3 \bmod 6, \quad x \equiv \bmod 7 \Leftrightarrow x \equiv 207 \bmod 210$]

GRP 2 nr 3

(1374)(15763)(12)(142)=(415)(76)(12)(142)=(415)(12)(142)(67)=(45)(67).

GRP 2 nr 13

Lad $\sigma\in\Sigma_n$ være en bijektiv afbildning af $\mathbf{n}=\{1,\ldots ,n\}$ på sig selv. Mængden n er udstyret med $(n-1)+\cdots + 1=\frac{1}{2}n(n-1)$ ulighedstegn. Lad $0\leq\mathcal{l}(\sigma)\leq\frac{1}{2}n(n-1)$ være antallet af ulighedstegn som bliver vendt af $\sigma$. Så gælder
  $$\begin{align}\mathcal{l}(\sigma)&=0 \Leftrightarrow \text{$\sigma$\space bevar... ...l{l}}(\sigma)-1 & \text{$\sigma$\space vender $i<i+1$ } \end{cases}\end{align}$$
For at vise ligning (7), husk på: $\text{$\sigma$\space bevarer $i_1<i_2$\space og $i_2<i_3$ } \Rightarrow \text{$\sigma$\space bevarer $i_1<i_3$ }$. Så hvis $\sigma$ vender præcis én ulighed i<j, så må det være en ulighed mellem naboer, j=i+1. Da

$$\underbrace{\sigma(1),\ldots ,\sigma(i+1)}_{\text{$i+1$\space... ...rbrace{\sigma(i),\ldots ,\sigma(n)}_{\text{$n-i+1$\space tal}}$$

er $\sigma(i+2),\ldots ,\sigma(n) \geq i+2$ og $\sigma(1),\ldots ,\sigma(i-1) \leq i-1$ og $\sigma$ er identiteten på ${\mathbf n} \setminus \{i,i+1\}$. Altså er $\sigma=(i \, i+1)$. Ligning (8) følger af at transpositionen $(i\, i+1)$ vender uligheden i < i+1 og ikke andre. Hvis $\sigma$ er et produkt af r transpositioner $(i\, i+1)$, så er ${\mathcal l}(\sigma)=(-1)^r=\mathrm{sign}(\sigma)$.

GRP 3 nr 3

$1 \xrightarrow{ \cdot 3} 3 \xrightarrow{ \cdot 3} 9 \xrightarrow{ \cdot 3} 10... ...12 \xrightarrow{ \cdot 3} 2 \xrightarrow{ \cdot 3} 6 \xrightarrow{ \cdot 3} 1$
[Der er andre muligheder.]