# Need to understand Lagrange's theorem and how it's applied in RSA

When I first started studying RSA, I found that I need to know Euler's theorem, to understand that I need Fermat's theorem, and to understand that, I need the order theorem of Lagrange which I am trying but don't understand as I never had mathematics as a subject. Everything I did is from my own.

I want to understand more visually rather than just maths.

I reckon from other posts, that to understand the relation of $$N$$ in RSA which is the composite prime of $$pq$$, with the Totient of $$N$$, I need to understand group and order. Which I don't. Other problems of RSA are for crypto.exchange. But this part of maths I want to understand first.

If you would be kind enough to explain, I would be so glad. Thanks :)

## 1 Answer

Lagrange's theorem is one of the most useful theorems in group theory. It just says that the order of any subgroup of a finite group $$G$$, divides the order of the group. That is, $$H\le G\implies |H|||G|$$.

Lagrange's theorem implies Fermat's little theorem, because the multiplicative group of the field of order $$p$$ has order $$p-1$$. Hence the order of any element $$a$$ such that $$(a,p)=1$$ must divide $$p-1$$. So $$a^{p-1}\cong1\pmod p$$.

You don't actually need Fermat's little theorem to understand Euler's theorem: more the other way around. The former is a special case of the latter. That is, Euler's theorem generalizes Fermat's little theorem to $$(a,n)=1\implies a^{\varphi(n)}\cong1\pmod n$$, where $$\varphi$$ is Euler's totient function. The totient function counts the number of relatiely prime numbers to n less than n, also called totatives. Thus $$\varphi(p)=p-1$$.

Not sure about the applications to cryptography. I have used these ideas in group theory and number theory more. Maybe you could ask a specific question from cryptography and we could try to answer it. For the applications I refer you to this answer: https://math.stackexchange.com/a/20193/403337.