

%begin macros
%\magnification=\magstephalf
\magnification=\magstep1
\def\g{\bigtriangledown}
\def\L{{\cal L}}
\def\Z{{\cal Z}}
%\baselineskip=14pt
%\parskip=10pt
\def\Tilde{\char126\relax}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\nopagenumbers
%end macros

\bigskip
{\bf MATH 356, Dr. Z. ,  Solutions to Exam I, Mon., Oct.  14, 2013, 
10:20-11:40am, SEC-218}
\bigskip
{\bf 1}. (10 pts.)  
Solve, if possible, the following linear congruences
$$ 
3x \equiv 8 \pmod {35}
$$


\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $x=26+35k \quad , k \in \Z$ 

OR 

$x \equiv 26 \pmod{35}$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
We first find $[3^{-1}]_{35}$ aka as $3^{-1}\pmod{35}$, by applying the extended Euclidean algorithm to $gcd(35,3)$.
$$
{\bf 35} = 11 \cdot {\bf 3} +2  \quad, \quad hence \quad 2={\bf 35} - 11 \cdot {\bf 3} \quad.
$$
$$
{\bf 3} = 1 \cdot 2 +1 \quad, \quad hence \quad 1={\bf 3} - 1 \cdot 2 = {\bf 3} - 1 \cdot ({\bf 35} - 11 \cdot {\bf 3}) =
12 \cdot {\bf 3} -{\bf 35} \quad .
$$
So we got
$$
12 \cdot {\bf 3} -{\bf 35} =1 \quad .
$$
Taking it modulo $35$ we get:
$$
12 \cdot {\bf 3} \equiv 1\pmod{35} \quad.
$$
Hence $[3^{-1}]_{35}=12$.

{\bf Now} to solve $3x \equiv 8 \pmod {35}$ we multiply by $8$ and take it modulo $35$:
$$
12 \cdot 8 \,\, modulo \,\, 35 = 96 \,\, modulo \,\, 35 = 2 \cdot 35 + 26 \,\, modulo \,\, 35 = 26 \quad.
$$
So the answer is $x \equiv 26\pmod{35}$ or $26+35k, k \in \Z$.

\vfill\eject


{\bf 2}. (10 pts.)   Find the two last (decimal) digits of $1013^{17}$
\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   $33$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
We need to do everything modulo $100$
$$
13^1 \,\, modulo \,\, 100 =13
$$
$$
13^2 \,\, modulo \,\, 100 =169 \,\, modulo \,\, 100 = 69=-31
$$
$$
13^4 \,\, modulo \,\, 100 =(-31)^2 \,\, modulo \,\, 100 =31^2 \,\, modulo \,\, 100 
= 61
$$
$$
13^8 \,\, modulo \,\, 100 = 61^2 \,\, modulo \,\, 100 = 21
$$
$$
13^{16} \,\, modulo \,\, 100 =  21^2 \,\, modulo \,\, 100 = 41
$$
Finally
$$
13^{17} \,\, modulo \,\, 100 =13 \cdot 41 \,\, modulo \,\, 100 =33 \quad .
$$

\vfill\eject


{\bf 3}. (10 pts.)  
Find out whether it is possible to express $1$ as a linear combination 
$$
1=m \cdot 44 +n \cdot 91 \quad ,
$$ 
for some integers $m$ and $n$, and if it is possible, find it.

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $m= -31$ \quad \quad $n=15$ \quad \quad \quad .
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
We first do the abbreviated Euclidean algorithm to find the gcd of $91$ and $44$
$$
gcd(91,44)=gcd(44,3)=gcd(2,1)=1 \quad .
$$
So the gcd is indeed $1$ and it is possible.

({\bf Note}: if the gcd would not have been $1$, then the answer would have been `not possible' and it would have
been stupid to do the much more time-consuming Extended Euclidean algorithm).

Now we must apply the extended Euclidean algorithm to $gcd(91,44)$.
$$
{\bf 91} = 2 \cdot {\bf 44} + 3 \quad hence \quad 3= {\bf 91} - 2 \cdot {\bf 44} \quad .
$$
$$
{\bf 44} = 14 \cdot 3 + 2  \quad ,
$$
hence
$$
2= {\bf 44} - 14 \cdot 3= 
{\bf 44} - 14 \cdot ( {\bf 91} - 2 \cdot {\bf 44})
$$
$$
={\bf 44} - 14 \cdot  {\bf 91} + 28 \cdot {\bf 44}= 29 \cdot {\bf 44} - 14 \cdot  {\bf 91} 
\quad .
$$
So $2= 29 \cdot {\bf 44} - 14 \cdot  {\bf 91}$.
Next
$$
3= 1 \cdot 2 +1 \quad ,
$$
hence 
$$
1=3 - 1 \cdot 2 = ({\bf 91} - 2 \cdot {\bf 44}) - 1 \cdot (  29 \cdot {\bf 44} - 14 \cdot  {\bf 91} )=
{\bf 91} - 2 \cdot {\bf 44} -  29 \cdot {\bf 44} + 14 \cdot  {\bf 91} ) =
15 \cdot {\bf 91} - 31 \cdot {\bf 44} \quad .
$$
So
$$
1=- 31 \cdot {\bf 44} \quad + 15 \cdot {\bf 91} \quad ,
$$
and we get $m=-31$ and $n=15$.

{\bf Note:} It is always good to check that the identity that you got at the end is correct.
If you made a computational error and you realize that your answer is erroneous, and
state so, you would get more partial credit if you do not check and give the wrong answer.

\vfill\eject


{\bf 4}. (10 pts.)  Find  the set of divisors of $105$

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $Div(105)=\{1,3,5,7,15,21,35,105 \}$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
$$
105=  3^1 \cdot 5^1 \cdot 7^1 \quad,
$$
hence
$$
Div(105)= \{1,3\} \times \{1,5\} \times \{1,7\}
$$
We first do
$$
\{1,3\} \times \{1,5\} = \{1,3,5,15 \} \quad .
$$
Next:
$$
Div(105)= (\{1,3\} \times \{1,5\}) \times \{1,7\}  =\{1,3,5,15 \} \times \{ 1, 7 \}=
\{1,3,5,15, 7, 21, 35, 105 \}=
\{1,3,5,7, 15, 21, 35, 105 \} \quad .
$$
\vfill\eject


{\bf 5}. (10 pts.)  Express $25025$ as a product of prime powers.

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   $5^2 \cdot 7 \cdot 11 \cdot 13$ \quad . (or in Maple: $[[5,2],[7,1],[11,1],[13,1]]$)
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
$25025$ is not divisible by $2$ (since it is odd), neither is it divisible by $3$, (since the sum of the digits $14$ is not divisible by $3$),
but since the last digit is $5$, it is divisible by $5$.

$25025/5=5005$, so $25025= 5 \cdot 5005$. $5005$ is still divisible by $5$ so $5005=5 \cdot 1001$, and we get
$$
25025=5^2 \cdot 1001 \quad .
$$

$1001$ is divisible by $7$ since $1001/7=143$ is an integer so
$$
1001= 7 \cdot 143 \quad .
$$
$143$ is divisible by $11$ since $143/11=13$, so
$$
143=11 \cdot 13 \quad .
$$
Finally $13$ is a prime and we are done.
Going back, we have
$$
1001= 7 \cdot 11 \cdot 13 \quad ,
$$
and
$$
250025= 5^2 \cdot 7 \cdot 11 \cdot 13 \quad .
$$

\vfill\eject


{\bf 6}. (10 pts.)  

Recall that the {\it Euclid-Mullin sequence}  is defined by
$M_1=2$, and for $n>1$, $M_n$ is the smallest prime divisor of $M_1 \cdot M_2 \cdots M_{n-1}+1$.

Find the first {\bf five} terms of the Euclid-Mullin sequence.

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   $M_1=2$ \qquad ,  \qquad 
$M_2=3$ , \qquad $M_3=7$,  
\qquad $M_4=43$, \qquad  $M_5=13$ \qquad .
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
$M_2:=M_1+1=3$ is a prime, hence the ``smallest prime dividing it'' is itself, so $M_2=3$.

$M_1 M_2+1=2 \cdot 3 +1=7$ is a prime, hence the ``smallest prime dividing it'' is itself, so $M_3=7$

$M_1 M_2 M_3+1=2 \cdot 3 \cdot 7+1=43$, is a prime, hence the ``smallest prime dividing it'' is itself, so $M_4=43$.

$M_1 M_2 M_3 M_4+1=2 \cdot 3 \cdot 7 \cdot 11+1=1807$, is too big to know by heart, so let's try to
see whether it has prime divisors. The worst that we have to go to is the largest prime $\leq \sqrt{1807}$ that
is $41$, but let's hope for the best.

Obviously, we don't have to check divisibility by $2,3,7$ and $43$. Since it does not end in $5$,
we can start with $11$. Since the alternating sum of the digits  $1-8+0-7=-14$ is not a multiple of $11$,
it is not divisible by $11$ (Lecture 12, coming up). Next we try $1807/13$ and surprise! it is an integer (namely $139$ but the exact value is
not relevant). So the smallest prime dividing $1807$ is $13$ and $M_5=13$.


\vfill\eject


{\bf 7}. (10 pts.)  
Express the integer $301$ (written in our usual (base 10) notation)
in  base $5$, in (i) sparse notation (4 pts) (ii) dense notation (3 pts) (iii) base-five positional notation (3 pts)

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  (i) $2 \cdot 5^3 + 2 \cdot 5^2 + 1 \cdot 5^0$
\bigskip
(ii) $2 \cdot 5^3 + 2 \cdot 5^2 + 0 \cdot 5^1+ 1 \cdot 5^0$
\bigskip
(iii) $2201$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
We list the powers of $5$: $1,5,5^2=25, 5^3=125, 5^4=625, \dots$ until we get a power that is
larger than our number. The power right below is the leading power.

Dividing our number, $301$, by $125$ we get $301=2 \cdot 125 +51$.

The largest power of $5$ smaller than $51$ is $5^2=25$.

Dividing $51$, by $25$ we get $51=2 \cdot 25 +1$.

Of course $1$ is $1$.

So the sparse representation is:
$$
301= 2 \cdot 5^3 + 2 \cdot 5^2 + 1 \cdot 5^0 \quad.
$$

To get the dense representation we pad it with the powers of $5$ that did not show up, and stick a $0$ in front of them.

$$
301= 2 \cdot 5^3 + 2 \cdot 5^2 + 0 \cdot 5^1 + 1 \cdot 5^0 \quad.
$$

Finally, to get the positional notation (base $5$) we just list the coefficients
$$
301= 2201 \, (base \,\, five) \quad .
$$
\vfill\eject


{\bf 8}. (10 pts.)  
Use Karatsuba's algorithm (no credit for other methods!), to find
the product
$$
99 \cdot 53 \quad .
$$
{\bf Reminder}: $(10a+b)(10c+d)= 100ac+ 10( (a+b)(c+d)-ac-bd))+ bd$ .

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $5247$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
$a=9$, $b=9$, $c=5$, $d=3$

$$
a \cdot c =45 \quad, \quad
b \cdot d = 27\quad, \quad
(a+b)(c+d)=18 \cdot 8 =144
$$
So far we only did {\bf three} multiplications!
Finally
$$
(a+b)(c+d)-ac-bd=144-45-27=72 \quad.
$$
Putting it all together
$$
99 \cdot 53 = (9 \cdot 10 +9)(5 \cdot 10 +3)= 10^2 \cdot 45 + 10^1 \cdot 72 + 27=
4500+720+27=5247 \quad .
$$
\bigskip
{\bf Comment}: Those who computed the middle term  $(a+b)(c+d)-ac-bd$ by doing instead $ad+bc$ got at most
half credit. They performed {\bf four} multiplications, and the whole point here is to only use {\bf three} multiplications.


\vfill\eject


{\bf 9}. (10 pts.)  
Let $F_n$ be the Fibonacci numbers.
Give a Zeilberger-style proof of the following identity, using $N_0=3$, of the identity
$$
\sum_{i=1}^{2n-1} F_i F_{i+1} = F_{2n}^2 \quad .
$$

{\bf Disclaimer:} To get a fully rigorous proof, we need $N_0=5$, but I am being nice, so I only ask you to do
it for $n=1,2,3$, so this is a semi-rigorous proof.
\bigskip
First let's recompute the Fibonacci numbers.
$$
F_1=1 \quad, \quad
F_2=1 \quad, \quad
F_3=2 \quad, \quad
F_4=3 \quad, \quad
F_5=5 \quad, \quad
F_6=8 \quad .
$$

Next, let's spell out the identity for $n=1,n=2,n=3$.
For $n=1$ this says:
$$
\sum_{i=1}^{1} F_i F_{i+1} = F_{2}^2 \quad .
$$
For $n=2$ this says
$$
\sum_{i=1}^{3} F_i F_{i+1} = F_{4}^2 \quad .
$$
For $n=3$ this says
$$
\sum_{i=1}^{3} F_i F_{i+1} = F_{6}^2 \quad .
$$

In everyday language. 
For $n=1$:
$$
F_1 \cdot F_2 = F_2^2
$$
And indeed
$$
1 \cdot 1 = 1^2 \quad
$$


For $n=2$:
$$
F_1 \cdot F_2 + F_2 \cdot F_3  + F_3 \cdot F_4 
= F_4^2
$$
And indeed
$$
1 \cdot 1+ 1 \cdot 2 + 2 \cdot 3 = 3^2 \quad
$$
(since $1+2+6=9$)



For $n=3$:
$$
F_1 \cdot F_2 + F_2 \cdot F_3  + F_3 \cdot F_4  +  F_4 \cdot F_5 +  F_5 \cdot F_6 
= F_6^2
$$
And indeed
$$
1 \cdot 1+ 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 5 + 5 \cdot 8= 8^2 \quad
$$
(since $1+2+6+15+40=64$). QED! ( at least according to Zeilberger).




\vfill\eject


{\bf 10}. (10 pts.)  

Use the Fundamental Theorem of Discrete Calculus  to prove
$$
\sum_{i=1}^{n} 3^i = \frac{3}{2}(3^{n}-1) \quad .
$$
\bigskip
Calling the right side $S(n)$ and the summand $a(i)$, we have to prove {\bf two things}.

(i) $S(0)=0$

(ii) $S(n)-S(n-1)=a(n)$.

In this problem $S(n)= \frac{3}{2}(3^{n}-1)$ and $a(i)=3^i$, so $a(n)=3^n$.

(i) is easy (but has to be checked!). $S(0)= \frac{3}{2}(3^{0}-1)=0$.

As for (ii)
$$
S(n)-S(n-1)=
 \frac{3}{2}(3^{n}-1) - \frac{3}{2}(3^{n-1}-1) 
=\frac{3}{2}(3^n-1-3^{n-1}+1)
$$
$$
=\frac{3}{2} (3^n-3^{n-1})=\frac{3}{2}(3^{n-1} \cdot (3-1))
=\frac{3}{2} (3^{n-1} \cdot (2))=3 \cdot 3^{n-1} =3^n= a(n)\quad .
$$
QED!

\end



