Modular arithmetic query

garo · 2020-06-08, 11:43

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

$(g^{a}\ mod\ p) \cdot (g^{b}\ mod\ p) \ mod\ p\equiv g^{(a+b)\ mod\ (p-1)}\ mod\ p$

retina · 2020-06-08, 11:53

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:

Originally Posted by garo

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)?

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.

2020-06-08, 11:43	#1
garo Aug 2002 Termonfeckin, IE 2⁴×173 Posts	Modular arithmetic query Apologies if this is very basic. Could anyone tell me why $(g^{a}\ mod\ p) \cdot (g^{b}\ mod\ p) \ mod\ p\equiv g^{(a+b)\ mod\ (p-1)}\ mod\ p$ Last fiddled with by garo on 2020-06-08 at 11:47

2020-06-08, 12:15	#5
garo Aug 2002 Termonfeckin, IE 5320₈ Posts	Gotcha. Thanks for your help. Not sure why I was making it more complicated in my head. Last fiddled with by garo on 2020-06-08 at 12:16

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
modular arithmetic	science_man_88	Miscellaneous Math	42	2011-07-26 02:02
modular arithmetic problem	JuanTutors	Math	4	2009-03-11 16:06
need C/C++ modular arithmetic code for Windows	ixfd64	Programming	15	2008-07-30 03:52
Modular Arithmetic	Numbers	Math	27	2005-11-30 15:41
Jim Howell's modular arithmetic program?	ixfd64	Software	0	2004-05-27 05:42

2020-06-08, 11:53	#2
retina Undefined "The unspeakable one" Jun 2006 My evil lair 2×3²×7×53 Posts	Because: https://en.wikipedia.org/wiki/Euler%27s_theorem

2020-06-08, 12:07	#3
garo Aug 2002 Termonfeckin, IE AD0₁₆ Posts	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)?