1.1 Introduction to elementary Calculus formulae
To thoroughly study and understand this module on Binomial Theorem, we’ll need to understand a couple of basic notations of Calculus and Number Theory to begin with. We’ll cover these topics in detail later on, when the time is right, but for now, let’s concentrate on arming ourselves with the few key things to better handle this module.
\(\frac{d}{dx}x^n=nx^{n-1}\). Also \(\frac{d}{dx}cx^n=c\frac{d}{dx}x^n=cnx^{n-1}\), where \(c\) is a constant independent of x. Also, derivative of a constant is 0.
This is called the differential of \(x^n\) with respect to \(x\). In this case, \(n\) may be any rational number. The way we derive this relation is a course for advanced calculus, and we’ll hint at that later on. For now, this is what we’ll need in a lot of cases for computing Binomial Sums.
Thus, \(\frac{d}{dx}x^3=3x^2\), \(\frac{d}{dx}\sqrt{x}=\frac{1}{2\sqrt{x}}\), and so on. The derivative of a function \(f\) at a point \(x_0\) basically denotes the slope of the curve of \(f\) at \((x_0,f(x_0))\).
We’ll now take a look at the anti-derivative, or the inverse of differentiation, i.e. integration.
\(\int x^ndx=\frac{x^{n+1}}{n+1}+C\), where \(C\) is a constant.
Look at this way, if you differentiate the R.H.S with respect to x, you’ll get L.H.S. In other words, if we calculate the derivative of L.H.S using what the formulae stated earlier, we get \(\frac{d}{dx}\left( \frac{x^{n+1}}{n+1}\right)=\frac{1}{n+1}\frac{d}{dx}x^{n+1}=\frac{(n+1)x^n}{n+1}=x^n=\text{R.H.S}\).
One result that we’d particularly need in this module is \(\int(1+x)^ndx=\frac{(1+x)^{n+1}}{n+1}+C\). This, will be thoroughly derived, when we shall take up Integral Calculus.
The integrals we looked above are indefinite integrals. We define an integral to be a definite integral, when the integration happens between limits. For example, lets consider \(\int f(x)dx=F(x)+C\). This is an indefinite integral.
\(\int_a^bf(x)dx=F(a)+C-F(b)-C=F(a)-F(b)\), this is what we call as a definite integral.
2.1 Introduction to Modular Arithmetic
Let’s take a quick look at the concepts of modular arithmetic, or congruencies.
In the world of positive integers, we represent, by the notation \(a\equiv b(\text{mod n})\), the fact that \(a\), when divided by \(n\), leaves a remainder \(b\).
Congruences satisfy the following properties:
a) \(a\equiv b(\text{mod n})\Rightarrow a^x\equiv b^x(\text{mod n})\)
b) \(a\equiv b(\text{mod n})\) and \(c\equiv d(\text{mod n})\Rightarrow a+c\equiv b+d(\text{mod n})\)
c) \(a\equiv b(\text{mod n})\) and \(c\equiv d(\text{mod n})\Rightarrow ac\equiv bd(\text{mod n})\)
2.2 Euler’s Totient Theorem
The totient function, denoted by \(\phi(n)\), denotes the number of numbers less than \(n\), that are relatively prime to \(n\). Euler extended this totient function to an important modular arithmetic theorem, which states
\(a^{\phi(n)}\equiv 1(\text{mod n})\), for relatively prime positive integers \(a,n\). Note that for any prime number \(p\), this theorem boils down to \(a^{p-1}\equiv 1(\text{mod p})\).
Let \((p_1,p_2,…p_r)\) be the set of primes that can divide \(n\). Then we have
\(\phi(n)=n\prod\limits_{i=1}^{r}\left(1-\frac{1}{p_i}\right)\)
One important result, which will be necessary to calculate the last 2 digits of higher powers, is that \(\phi(100)=100\times\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=40\).
Thus, for any number \(a\) with \(\text{GCD(a,100)=1}\), we can conclude \(a^{40}\equiv 1\text{(mod 100)}\). Note that the last 2 digits of a number is the number modulo 100.
Ex -1
Calculate the last 2 digits of \(3^{83}\).
Solution:
We have 3 and 100 as co-prime integers, thus we can apply Euler’s Totient theorem to calculate \(3^{40}\equiv 1\text{(mod 100)}\Rightarrow (3^{40})^2\equiv 1^2\text{(mod 100)}\Rightarrow 3^{80}\equiv 1\text{(mod 100)}\).
Now we know that \(3^3\equiv 27\text{(mod 100)}\), thus multiplying this with \(3^{80}\equiv 1\text{(mod 100)}\) gives \(3^{83}\equiv 27\text{(mod 100)}\). Thus 27 are the last 2 digits of \(3^{83}\).
Similarly, we can use \(\phi(1000)=400\) to calculate modulo 1000, which will give us the last 3 digits of a number.
We need to keep 2 points in mind whenever we are dealing with such problems:
- Although, these concepts provide a quick methodology to calculate the last 2 or 3 digits of a number, it may often become cumbersome and time taking. We’ll illustrate an alternate way to calculate these using the Binomial Theorem as well. It’s a tradeoff that students would need to make when to use what, usually, if the modulo relationships arrive immediately after looking at the problem statement, it’s a hint that taking this approach may save your time.
- The remainders that we have, can also be negative in nature, and it’s often useful to use this ‘negative’ aspect of the numbers. For example, let’s assume that we may need to find the remainder of \(7^7\), when divided by \(50\). In this case, it’s useful to have \(7^2\equiv -1\text{(mod 50)}\) rather than having \(7^2\equiv 49\text{(mod 50)}\). In the first scenario, we can just cube both the sides to give \(7^6\equiv (-1)^3\text{(mod 50)}\). Thus we have \(7^6\equiv -1\text{(mod 50)}\). Now multiplying both sides by \(7\), we have \(7^7\equiv -7\equiv 43\text{(mod 50)}\).