I am not sure how to prove this: If a has order t modulo a prime p, show that a^(t-1)+a^(t-2)+...+a+1 == 0(mod p).
Follow Math Help Forum on Facebook and Google+
Originally Posted by tarheelborn I am not sure how to prove this: If a has order t modulo a prime p, show that a^(t-1)+a^(t-2)+...+a+1 == 0(mod p). since . Note that it's necessary that , otherwise doesn't exist modulo .
I can't untangle the algebra of this move... Sorry, can you break it down into a couple of steps? Thanks.
Originally Posted by tarheelborn I can't untangle the algebra of this move... Sorry, can you break it down into a couple of steps? Thanks. This is a geometric series. What do you get when you multiply ?
You would get (a*a^(t-1)+a*a^(t-2)+...+a^2+a-a^(t-1)-a^(t-2)-1), right?
Originally Posted by tarheelborn You would get (a*a^(t-1)+a*a^(t-2)+...+a^2+a-a^(t-1)-a^(t-2)-1), right? Correct, now notice how the majority of the terms cancel out, so you end up with .
Yes, actually I did notice that...
So since a^t == 1 (mod p), (a^t)-1 == 0 (mod p), is that the idea?
Originally Posted by tarheelborn So since a^t == 1 (mod p), (a^t)-1 == 0 (mod p), is that the idea? yep
View Tag Cloud