## ICQ, once a popular social communication tool

Posted: September 30, 2012 in Mathematics

God knows why I feel a sense of loss tonight and I found an old log file of an ICQ conversation. It’s over ten years old back in the year 99. I don’t know if any of you have ever been in the ICQ era before, it was a very popular messaging client before the msn overtook the world. Kind of like the Facebook today. Anyway there is a quote I wrote back then.

Life is like a journey. It will be an easy one. Or it may be a difficult one. But one thing should you remember, always make it a happy one!

## calculating mortgage the easy way!

Posted: September 29, 2012 in Mathematics

Have you ever wondered how to calculate mortgage by hand?  I am taking about figuring it out on a piece of paper with just pencil and calculator.  Without the mortgage table, fancy formulas, mortgage solver programs you can easily find on the internet, or any other helps.  Alright let’s begin.

First the definitions:

• A = The mortgage amount
• n = number of payments
• r = interest rate of each payment period, usually monthly interest or $\frac{\mbox{annual interest}}{12}$
• p = the payment amount

Assume the payment is due at the end of each month, then the amount own in the first month will be charged an interest $A(1+r)$.  After the mount p is pay, the bill of the second month will be $(A(1+r)-p)(1+r)$.  And by the nature of mortgage, everything has to pay off at the end.  Hence we can come up with this equation,

$((A(1+r)-p)(1+r)-p)(1+r)-...-p=0$

Now expand the left side,

$A(1+r)^n-p(1+r)^{n-1}-...-p(1+r)-p=0$

$A(1+r)^n=p+p(1+r)+\ldots+p(1+r)^{n-1}$

Then apply the sum of geometric series,

$A(1+r)^n=\displaystyle{p}\left(\frac{1-(1+r)^n}{1-(1+r)}\right)=p\left(\frac{(1+r)^n-1}{r}\right)$

$p=\displaystyle\frac{Ar(1+r)^n}{(1+r)^n-1}$

$p=\displaystyle\frac{Ar}{1-(1+r)^{-n}}$

For example, a mortgage of $1,000,000 with monthly payment over 25 years at an annual interest rate of 3%. By the above formula, $p=\displaystyle\frac{1000000(0.03/12)}{1-(1+0.03/12)^{-300}}=4742.11$ The monthly payment is$4,742.11

Remark:

The other way of formulating the equation is to partition the mortgage amount A into n pieces,

$A=A_1+A_2+\ldots+A_n$

each $A_i$ is different in size, then for each $A_i$,

$A_i(1+r)^i=p$

$A_i=\displaystyle\frac{p}{(1+r)^i}$

then,

$A=\displaystyle\frac{p}{1+r}+\frac{p}{(1+r)^2}+\cdots+\frac{p}{(1+r)^n}$

$A=\displaystyle\frac{p}{1+r}\left(\frac{1-(1+r)^{-n}}{1-(1+r)^{-1}}\right)=\frac{p(1-(1+r)^{-n})}{r}$

$p=\displaystyle\frac{Ar}{1-(1+r)^{-n}}$

## measuring 9 minutes with a 4 minute sandglass and a 7 minute sandglass

Posted: September 27, 2012 in Mathematics

Looking for a job isn’t easy nowadays.  There is a rumor that in Google, they will ask you some questions in the interview to test your problem solving skill.  One of the questions I saw on a forum is:

“How do you measure exactly 9 minutes with only a 4 minutes sandglass and a 7 minute sandglass in your hand?”

I spent about couple minutes in front of the computer while watching “How I meet your mother” online then I come up with my solution.

First start with both sandglass.  When the 4 minute sandglass done dripping, you know 4 minutes are gone.  Now you should have 3 minutes of sand in the 7 minute sandglass, turn the 4 minute sandglass upside down.  Wait until the remaining 3 minutes of sand in the 7 minute sandglass is done, that’s a total of 7 minutes are gone.  While there is 1 minute of sand left in the 4 minute sandglass, you flip the 7 minutes sandglass.  A minute later, that should be 8 minutes in total, the 4 minute sandglass is done.  There should be 1 minute of sand at the bottom of the 7 minute sandglass.  And now you flip that 7 minute sandglass.  At the end the 7 minute sandglass should finish in 1 minute, which is 9 minutes in total.  We are done!

Back to How I met your mother 🙂 I may not be smart enough to get a job at Google.

Ciao

## modular arithmetic with large numbers

Posted: September 24, 2012 in Mathematics
Tags: , , , ,

In elementary school, we learn division and quite often when a number is divided by a divisor we don’t exactly get the answer without remainder.  For example, when a number 14 is divided by 3 then the quotient is going to be 4 with the remainder 2.  Because of the following,

$14=3\cdot4+2$

Now if we translate this into modular arithmetic, it becomes:

$14\equiv2\quad\mbox{ mod } 3$

Now this seems easy everyone can do it.  But what if someone asks you to find a remainder when $2^{99}$ is divided by 15?  If you do it the way a grade 4 student does, you will first of all need to compute the monster $2^{99}$ which is quite impossible for any mortals to calculate by hand and even with a scientific calculator.  And not to mention dividing that huge number by 15 which will take probably another life time to do it by hand.  Fortunately there is a way to compute all that stuffs.  Since

$2^4\equiv16\equiv1 \quad\mbox{ mod }15$

then we have

$2^{99} \equiv 2^{4\cdot24+3} \equiv (2^4)^{24}\cdot2^3 \equiv 1\cdot8 \equiv 8\quad\mbox{ mod }15$

Now this seems easy isn’t it?  I am sure everyone can do it.  Let’s do something more interesting.  I saw this problem last week on a forum.  Find the last five digits of $32141^{43210}$.  Ok, this is an interesting one 🙂  So I shall give two different ways to solve this for the readers.  Notice that this is the same as asking to find $32141^{43210} \quad\mbox{ mod } 100000$

<< Method 1 >>

In this solution, I am going to apply Euler’s Theorem and Chinese Remainder Theorem.

The reason that Chinese Remainder Theorem is necessary in here is because the number 100000 isn’t prime.  And we can factor 100000 into two numbers which are relatively prime to each other as,

$100000=10^5=2^5 5^5=32 \cdot 3125$

then we find their Euler’s phi function,

$\phi(32)=16, \qquad \phi(3125)=2500$
By the Euler’s Theorem, if $(a,n)=1$, then

$a^{\phi(n)} \equiv 1 \mbox{ mod } n$

Since 2 and 5 do not divide 32141 we have,

$32141^{16} \equiv 1 \quad\mbox{ mod } 32$

$32141^{2500} \equiv 1 \quad\mbox{ mod } 3125$

then

$32141^{43210} \equiv 32141^{10} \quad\mbox{ mod } 32$

Since $32141=32\cdot1004+13$

We have $32141^{10} \equiv 13^{10} \quad\mbox{ mod }32$

Here we can use “the power of 2” trick to reduce this since,

$13^2\equiv169\equiv9$

$13^4\equiv81\equiv17$

$13^8\equiv289\equiv1\quad\mbox{ mod }32$

then

$13^{10} \equiv 13^8\cdot13^2 \equiv 1\cdot9 \equiv9\quad\mbox{ mod }32$

Therefore,

$32141^{43210} \equiv 32141^{10} \equiv 13^{10} \equiv 9 \quad\mbox{ mod }32$

similarly we have,

$32141^{43210} \equiv 32141^{710} \equiv 891^{710} \equiv 2651 \quad\mbox{ mod }3125$

Now we apply the Chinese Remainder Theorem, (see link for explanation)

$x=32141^{43210}, M=100000$

$a_1=9, m_1=32, a_2=2651, m_2=3125$

with $x\equiv a_1b_1\frac{M}{m_1}+a_2b_2\frac{M}{m_2} \mbox{ mod } M$

we need to solve

$3125b_1 \equiv 1 \mbox{ mod } 32$

and

$32b_2 \equiv 1 \mbox{ mod } 3125$

I will do the first one, and leave the second for reader.

$3125b_1\equiv1\mbox{ mod }32$

$21b_1\equiv1\mbox{ mod }32$

then apply the Euclidean Algorithm,

$32=21+11$

$21=11+10$

$11=10+1$

then we work it backward,

$1=11-10=32-21-(21-11)=32-2(21)+32-21=2(32)-3(21)$

hence,

$b_1 \equiv -3 \equiv 29 \mbox{ mod } 32$

Similarly,

$b_2 \equiv 293 \mbox{ mod }3125$

$\therefore 32141^{43210} \equiv 9(29)(3125)+2651(293)(32) \equiv 71401 \mbox{ mod }100000$

Remark:

There is also an easier way, since

$9 \mbox{ mod } 32 = 2651 \mbox{ mod } 3125$

then there exists an $n\in\mathbb{Z}$

$x=3125n+2651=9 (\mbox{mod }32)$

$21n+27=9$

$21n=-18$

$21n=14$

Since 7 and 32 are relatively prime, we can divide both sides by 7

$3n=2$

Since $66=2(32)+2$

$n=22$

$\therefore x=3125(22)+2651=71401$

<< Method 2 >>

This method here involves Binomial Theorem, which is faster in this case.

First, we will use a trick from Method 1 to reduce the power 43210 to 3210.

$\phi(100000)=16\cdot2500=40000$

$\therefore 32141^{43210} \equiv 32141^{3210}\mbox{ mod }100000$

Now apply Binomial theorem,

$(1+32140)^{3210} \qquad \mbox{mod }100000$

$=1+\binom{3210}{1}32140+\binom{3210}{2}32140^2+\binom{3210}{3}32140^3+\binom{3210}{4}32140^4$

Since $8|3214^4$ and $3|321$,

$\displaystyle\binom{3210}{4}32140^4=\frac{3210\cdot3209\cdot3208\cdot3207}{4\cdot3\cdot2}32140^4=0\mbox{ mod }100000$

$\displaystyle=1+321\cdot3214\mbox{ (mod }1000)\cdot100\\+\frac{321\cdot3209}{2}\cdot3214^2\mbox{ (mod }100)\cdot1000\\+\frac{321\cdot3209\cdot3208}{3\cdot2}\cdot3214^3\mbox{ (mod }10)\cdot10000$

$=1+321\cdot214\mbox{ (mod }1000)\cdot100\\+21\cdot9\cdot14\cdot7\mbox{ (mod }100)\cdot1000\\+7\cdot9\cdot4\cdot4^3\mbox{ (mod }10)\cdot10000$

$=171401=71401 \mbox{ mod } 100000$