please I need some help on these qustion
1) Use the theory of congruences to show that [89|(2^44) − 1].
2) For any n 2 N find the remainder when the number
1^5 + 2^5 + 3^5 + · · · + (n − 1)^5 + n^5
is divided by 4.
Hello,
I don't know how far you've studied these things... Nevermind...
We want to show that $\displaystyle 2^{44}\equiv 1 [89]$
The cardinal of (Z/89Z)* is 88 because 89 is a prime integer.
The elements of (Z/89Z)* are the positive integers <89 and coprime with 89. Because 89 is prime, any integer <89 will be coprime with 89. Hence, 2 belongs to (Z/89Z)*.
We know that the order m of an element belonging to (Z/89Z)*, here 2, divides its cardinal, 88.
Hence, $\displaystyle m \in \{1;2;4;8;11;22;44;88\}$
m is such as :
$\displaystyle 2^m \equiv 1 [89]$
$\displaystyle 2^m$ is $\displaystyle > 89$.
$\displaystyle \Longrightarrow m \neq 1;2;4$
Now, $\displaystyle 2^8=256=3*89-11 \equiv -11 [89]$
$\displaystyle 2^{11}=2^8 \cdot 2^3=2^8 \cdot 8 \equiv (-11) \cdot 8 [89]$
----> $\displaystyle 2^{11} \equiv -88 [89] \Longleftrightarrow 2^{11} \equiv 1 [89]$
$\displaystyle \boxed{2^{44}=(2^{11})^4 \equiv 1^4 [89]}$
QED.
For the second one :
We're looking for c : $\displaystyle (1^5+2^5+3^5+\dots+(n-1)^5+n^5) \equiv c [4]$
$\displaystyle 1^5 \equiv 1 [4]$
$\displaystyle 2^5=2^2 \cdot 2^3=4 \cdot 2^3 \equiv 0 [4]$
$\displaystyle 3^5=3^2 \cdot 3^2 \cdot 3 \equiv 1 \cdot 1 \cdot 3 [4] \Longleftrightarrow 3^5 \equiv -1 [4]$
$\displaystyle 4^5 \equiv 0 [4]$
$\displaystyle 5^5 \equiv 1 [4]$
$\displaystyle \dots$
Now, do you see any induction to this ?
Hint : the possible values for the remainder is either 0 either 1, all depends on the congruence of n to 4.
Note that a number a can be: $\displaystyle
a \equiv -1,0,1,2\left( {\bmod .4} \right)
$
We won't consider the even terms, since they're all multiple of 4.
Case $\displaystyle n = 2m - 1
$
$\displaystyle \sum_{k=1}^{m}{(2k-1)^5}\equiv{\sum_{k=1}^{m}{(-1)^{k-1}}
} (\bmod.4)$
Thus: : $\displaystyle \sum_{k=1}^{m}{(2k-1)^5}\equiv{
\frac{{1 - \left( { - 1} \right)^m }}{2} } (\bmod.4)$
Case $\displaystyle n = 2m
$
We get the same result, since the term we have added is even
Therefore the general result is: $\displaystyle \sum_{k=1}^n{k^5}\equiv{
\frac{{1 - \left( { - 1} \right)^{\left\lceil {\tfrac{n}
{2}} \right\rceil } }}
{2}}(\bmod.4)
$ where $\displaystyle
\left\lceil x \right\rceil
$ is the ceiling function