This note is about some math concepts that can be converted into \(\color{Red}{\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\).

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\).

\(\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

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)}\)

**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.

## Comments

Sort by:

TopNewestSuperb note! Also congrats on being selected as Moderator!! – Shreya R · 2 years, 1 month ago

Log in to reply

Of course this is a good idea, but as someone who has written Python code for a living I feel compelled to suggest a few improvements:

1) Finding modular inverse using brute force is exponential in the size of the input. We can easily make it polynomial by adapting Euclid's algorithm for GCD a bit:

2) Finding factorials is expensive. We can do much better by using a tuple as a representation of a fraction and using the fact that nCk = (n/k) x (n-1)C(k-1):

Alternatively, if you are okay with multiplying large numbers but don't like taking gcds each time,

3) For the gcd = 1 case we don't even need to keep the list:

For the gcd != 1 case we do need something but a dict is probably the better solution. Something like this:

Log in to reply

Congratulations Aditya on being selected as moderator – Usama Khidir · 2 years, 1 month ago

Log in to reply

– Aditya Raut · 2 years, 1 month ago

Thanks friend ! I'll give all efforts possible to make Brilliant free of problematic problems and spam comments...Log in to reply

Thank you. I know C , But not python. I will learn it. I love programming a lot. – পদ্মা মাঝি · 2 years, 1 month ago

Log in to reply

Sympy module in python is amazing. – Mharfe Micaroz · 1 year, 12 months ago

Log in to reply

Sir, How to create a program that inputs 2 numbers then get the GCF of it? in C language please. – Jep Iglesia · 2 years, 1 month ago

Log in to reply

@Jep Iglesia , I'm your age, 1 year younger as per what your account shows, So don't call me sir... I'm not knowing C that much, I learn Python..... but I've got a friend who can help you... I'll ask him to post that

@Aamir Faisal Ansari – Aditya Raut · 2 years, 1 month ago

Log in to reply

– Jep Iglesia · 2 years, 1 month ago

Sir Thank you sir. You know I'm used to call Sir/Ma'am in Internet. Its a kind of showing respect.Log in to reply

– Happy Melodies · 1 year, 11 months ago

Use Euclid Algorithm: see http://stackoverflow.com/questions/19738919/gcd-function-for-cLog in to reply

You guys may also want to look into IPython, Numpy, SciPy and Sage. – L N · 2 years, 1 month ago

Log in to reply

And for binomial coefficients:

Don't know about mod order, but there may be something like it in sage. Examples taken from the docs. This doesn't even scratch the surface of what you can do with Sage. – L N · 2 years, 1 month ago

Log in to reply

Log in to reply

COMBINATORICS, then it will print the number of ways in which the letters/numbers can be arranged. I am working on that, and will add when succeed. – Aditya Raut · 2 years, 1 month agoLog in to reply

Log in to reply

itertools library, which eliminates the need for all of these for loops.

There is also Python'sThe ''.join(p) converts ('A', 'B', 'C') to 'ABC', by joining all the letters together with the empty string, '' – Daniel Ploch · 2 years, 1 month ago

Log in to reply

– Aditya Raut · 2 years, 1 month ago

Wow, and if i want the number of permutations, then simply instead of "print" i can append to some list and then \(\textbf{len(list)}\) . Thanks a lot !Log in to reply

Log in to reply

– Chew-Seong Cheong · 2 years, 1 month ago

Thanks, Daniel. I have seen someone else using this. But I didn't know exactly how it is used. Now I know. Thanks.Log in to reply

– Chew-Seong Cheong · 2 years, 1 month ago

Thanks for the reply. I actually solved the COMBINATORICS problem on Brilliant.org. But I did it with a spreadsheet. I can actually do the permutation but I need to use 13 "for-in-range" statements since there are 13 letters to permutate. There is an built-in way.Log in to reply

itertoolsthere is a function calledproductwhich is an immense help when dealing with nested for loops. Let me give you an example:Is the same as...

Log in to reply

li=sorted(str) , then use the binomial definition in bove note and make it

binom(len(li) ,li.count(i) )

Then for next one (i+1), use binom(len(li)-li.count(li[i]) , li.count(li[i+1]) – Aditya Raut · 2 years, 1 month ago

Log in to reply

– Chew-Seong Cheong · 2 years, 1 month ago

Aditya, can you show an actual example. I will wait for your COMBINATORICS example. Thanks.Log in to reply

Awesome....Have you heard about pygame module of python @Aditya Raut ?If yes,have you created any game using it? – Harsh Shrivastava · 2 years, 1 month ago

Log in to reply

– Aditya Raut · 2 years, 1 month ago

Not heard, I am still a learner and I learn Python from self study... So I don't know what pygame is, will search !Log in to reply

– Harsh Shrivastava · 2 years, 1 month ago

Congrats for being selected as a moderator.Log in to reply