Exercise 9.44

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Let $n \in \Z$, $n = s_1\cdots s_t, n\equiv 1 \pmod 4, i = 1,\ldots,t$. Show $(n-1)/4\equiv \sum_{i=1}^t (s_i-1)/4 \pmod 4$.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof}
If  $n = s t , s \equiv1,t\equiv1\ [4]$, then $s = 4k+1, t = 4 l +1, k,t \in \mathbb{Z}$, so
$$n = (4k+1)(4l+1) = 16 kl + 4k+4l+1, \frac{n-1}{4} = 4 kl + k + l \equiv k+l = \frac{s-1}{4}+\frac{l-1}{4} \ [4].$$
Reasoning by induction on $t$, suppose that  every product of $t$ factors $ n = s_1s_2\cdots s_t$, where $s_i\equiv 1 \ [4]$ verifies 
$$\frac{n-1}{4} \equiv \sum\limits_{i=1}^t \frac{s_i-1}{4} [4].$$
If $n' = s_1 s_2 \cdots s_t s_{t+1} = n s_{t+1}, s_i \equiv 1[4]$, then $n\equiv1,s_{t+1} \equiv 1 \ [4]$, so
$$\frac{n'-1}{4} \equiv \frac{n-1}{4} + \frac{s_{t+1}-1}{4} \equiv \sum\limits_{i=1}^t \frac{s_i-1}{4} + \frac{s_{t+1}-1}{4} \equiv \sum\limits_{i=1}^{t+1} \frac{s_i-1}{4} \ [4].$$
Conclusion :  if  $n = s_1 s_2 \cdots s_t, s_i \equiv 1 [4]$, then $\frac{n-1}{4} \equiv \sum\limits_{i=1}^t \frac{s_i-1}{4} [4]$.
\end{proof}

Exercise 9.44

Answers

Comments

Exercise 9.44

Answers

Comments

Add answer