mersenneforum.org

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.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.