Lucas Theorem – Proof and Applications

forthright48 on November 16, 2018

Problem

Given non-negative integers $N$, $K$ and a prime number $P$, find the value of:

$$\binom{N}{K} \mod P$$

Sounds like a simple problem right? There are several ways to solve the problem, depending on the constraints of $N$, $K$, and $P$.

Direct: If $N$, $K$ are really small, less than $12$, then we can calculate $\binom{N}{K}$ directly using formula $\frac{N!}{K! \times (N-K)!}$ and find the mod $P$ value. Not gonna work when the values are around $1000$.
DP: If they are slightly bigger but still around $1000$, then we can use dynamic programming to find the result, using the recurrence: $\binom{N}{K} = \binom{N-1}{K} + \binom{N-1}{K-1}$. Not going to work if values are around $10^5$.
Modular Inverse: If $P$ is a large prime, say $10^9+7$, then using modular inverse and some precalculation we can still calculate $\frac{N!}{K! \times (N-K)!}$. But still, we will need to run $O(N)$ loop to calculate $N!$. Not going to work if $N$ is too large. Also, if $P$ is small then there won’t be any modular inverse since $P$ will not be coprime with denominator anymore.

So what do we do when $N$ and $K$ are large (let’s say around $10^9$) and prime $P$ is small, let’s say $37$. Is it still possible?

Of course. We use Lucas Theorem.

Chinese Remainder Theorem Part 2 – Non Coprime Moduli

forthright48 on November 18, 2017

As promised on the last post, today we are going to discuss the “Strong Form” of Chinese Remainder Theorem, i.e, what do we do when the moduli in the congruence equations are not pairwise coprime. The solution is quite similar to the one we have already discussed in the previous post, so hopefully, it will be a lot easier to understand.

Prerequisite

If you haven’t read my previous post, you can find it here: Chinese Remainder Theorem Part 1. I strongly suggest you read that one before proceeding onwards.

Problem

Given two sequences of numbers $A = [a_1, a_2, \dots, a_n]$ and $M = [m_1, m_2, \dots, m_n]$, find the smallest solution to the following linear congruence equations if it exists:

$$x \equiv a_1 \text{(mod } m_1) \\ x \equiv a_2 \text{(mod } m_2) \\ \dots \\ x \equiv a_n \text{(mod } m_n)$$

Note: The elements of $M$ are not pairwise coprime

Euler Phi Extension and Divisor Sum Theorem

forthright48 on September 26, 2015

Previously we learned about Euler Phi Function. Today we are going to look at two theorems related to Euler Phi that frequently appears in CPPS. I am not sure whether these theorems have any official names, so I just made them up. These allow easy references so I will be using these names from now on.

Euler Phi Extension Theorem

Theorem: Given a number $N$, let $d$ be a divisor of $N$. Then the number of pairs $\\{a, N \\}$, where $1 \leq a \leq N$ and $gcd(a,N) = d$, is $\phi(\frac{N}{d})$.