mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Other Mathematical Topics (https://www.mersenneforum.org/forumdisplay.php?f=117)
-   -   Modular arithmetic query (https://www.mersenneforum.org/showthread.php?t=25593)

 garo 2020-06-08 11:43

Modular arithmetic query

Apologies if this is very basic. Could anyone tell me why

[TEX](g^{a}\ mod\ p) \cdot (g^{b}\ mod\ p) \ mod\ p\equiv g^{(a+b)\ mod\ (p-1)}\ mod\ p[/TEX]

 retina 2020-06-08 11:53

Because: [url]https://en.wikipedia.org/wiki/Euler%27s_theorem[/url]

 garo 2020-06-08 12:07

Right. I got that far but couldn't make the connection. How do I get from the totient function to (a+b) mod (p-1)?

 retina 2020-06-08 12:09

[QUOTE=garo;547440]Right. I got that far but couldn't make the connection. How do I get from the totient function to (a+b) mod (p-1)?[/QUOTE]For primes the totient function is simply p-1. So multiples of p-1 in the exponent can be ignored.

 garo 2020-06-08 12:15

Gotcha. Thanks for your help. Not sure why I was making it more complicated in my head.

 All times are UTC. The time now is 22:15.