"Maths+Programming " makes life easier !

This note is about some math concepts that can be converted into $\color{#D61F06}{\textbf{Python programs}}$ that you can easily write, they'll define some useful things in maths, which are generally not in the modules, but are needed at times.

So, these programs can really help you reduce calculations, they can do the calculations for you...

New addition here

This is a program to print prime numbers till a range. (This is not written by me, but i felt like sharing because it's way useful)

Input $\textbf{get\_primes(n)}$ and it prints a list of all primes till the number $n$.

img

If you want it to get simple, just add the line $\text{li=get\_primes(n)}$ and then wanted changes in $li$.

$\mathbf{1.}\quad \quad\textbf{Inverse of a modulo b}$

$\bullet \quad$This function is defined for coprime integers $a$ and $b$, that $m$ is inverse of $a$ modulo $b$ if $\displaystyle m\times a \equiv 1 \pmod{b}$

$\bullet \quad$It is used when you want to perform actions like division in modulo, and also, it is used in the application of CRT (The Chinese Remainder Theorem).

$\bullet \quad$ The Python program that prints the Inverse of a number is as follows, after you type this program and input $\textbf{mod\_inv(a,b)}$ , it will return the inverse of $a$ modulo $b$.

img

$\mathbf{2.}\quad \quad\textbf{ Binomial Coefficient} \dbinom{a}{b}$

$\dbinom{a}{b}$ is the number of ways of choosing $b$ objects from a set of $a$ identical objects.

$\bullet \quad$It is defined as $\dbinom{a}{b} = \dfrac{a!}{b!(a-b)!}$ (where $a!$ is factorial notation)

$\bullet \quad$It is useful in many (almost all) Combinatorics Problems and some Number Theory problems can be designed on them.

$\bullet \quad$The Python program that prints $\dbinom{a}{b}$ value is as follows

mg

So when you input $\textbf{binom(a,b)}$ after typing this program, you'll obtain the output as $\binom{a}{b}$

$\mathbf{3.}\quad \quad\textbf{Order of a modulo b (a special case, of coprimes)}$

$\bullet \quad$It is defined as the number of congruences of powers of $a$, after which the remainder starts repeating.

For example,
$3\equiv 3 \pmod{5} \\ 3^2\equiv 4\pmod{5} \\ 3^3 \equiv 2 \pmod{5} \\ 3^4 \equiv 1 \pmod{5} \\ 3^5 \equiv 3 \pmod{5} \dots$

See that the congruence will repeat again after $3^5$, that means the remainder is repeating after multiplying by $3^4$, so order of $3$ modulo $5$ is $\boxed{4}$

$\bullet$ >>> Note that order can be mentioned as the least positive integer $m$ for which $a^m\equiv 1 \pmod{b}$ (This can be treated as the definition for $gcd(a,b)=1$).

It's easy to see that if $gcd(a,b) > 1$ , then we'll have, $a^m \equiv c \pmod{b} \implies gcd(a,b) \mid c$

For example, if $gcd(a,b)\neq 1$, say for numbers $8$ and $14$ ,

$\quad\quad\quad 8\equiv 8 \pmod{14} \\ \quad\quad\quad 8^2\equiv 8\pmod{14} \\\quad\quad\quad\quad\quad ... \\ \implies 8^n\equiv 8 \pmod{14}$

So order of 8 modulo 14 is $1$. (Though $8^1 \not\equiv 1 \pmod{14}$

This is an extremely important thing in modular arithmetic and tedious calculations of remainder are reduced to simpler ones.

However, it's not that easy to find order of larger integers modulo some other large integers. So here is the python code that prints Order of $a$ modulo $b$ ( if $gcd(a,b)=1$), when you input $\textbf{mod\_order(a,b)}$

img

Note+Exercise:- Try to extend this program to numbers with $gcd(a,b)\neq 1$ (A simple manipulation will do)

$\bullet$ This note might perhaps seem obvious to expert people, so note that it is for beginners and learners.

$\bullet$ When I think of some new program related to Maths, I will be adding to this note.

$\bullet$ If you all have any suggestions (additions), i would like to learn the new techniques of converting maths to Programming. Please comment and I will make sure it's included in the note.