Question about congruences and orders

[Ch1ronTL34]

The question is:

Show that if p is an odd prime and ord(p^a)a=2t, then
a^t== -1 mod p^a

First, I used ord(p^a)a to mean "order of a, mod p^a" and the == sign means congruent.

So first, I tried a few examples. Let p=3, a=2
Since ord(9)2=6, then t=3 and:
2^3 == -1 mod 9 TRUE

I continued with different values of p and a. Here is a table(sorry it looks weird):

p--a--t--p^a
3--2--3--9
5--2--10--25
11--2--55--121
13--2--78--169
17--2--68--289

It seems that p|t in all of my examples but I'm stuck...THANKS!

 

[matt grime]

If we take a^t and square it what do we get? Now, since a^t is not 1, since 2t is the order of a, what do you need to show?

 

[tacman]

It is a known fact that for any odd prime p, the order of p modulo p^a is p^(a-1)(p-1). This means that for any positive integer k such that p^a|k, the order of k modulo p^a is also p^(a-1)(p-1).

In this case, we are given that ord(p^a)a=2t. This means that the order of p^a modulo p^a is 2t. Since p^a|p^a, this means that the order of p^a modulo p^a is also 2t.

By the definition of order, this means that p^(2t)≡ 1 (mod p^a).

Now, we can use the fact that ord(p^a)a=2t to rewrite this as (p^(a-1)(p-1))^2t≡ 1 (mod p^a).

By the properties of congruence, this can be rewritten as p^(2t(a-1)(p-1))≡ 1 (mod p^a).

Since p is an odd prime, we can rewrite p^(2t(a-1)(p-1)) as (p^(a-1))^2t(p-1)^2t.

Using the fact that p^(a-1)≡ 1 (mod p^a), we can rewrite this as (1)^2t(p-1)^2t≡ 1 (mod p^a).

Simplifying, we get (p-1)^2t≡ 1 (mod p^a).

Now, we can use the fact that p is an odd prime to rewrite this as (-1)^2t≡ 1 (mod p^a).

Finally, simplifying, we get (-1)^t≡ 1 (mod p^a).

This is equivalent to saying that (-1)^t-1 is divisible by p^a, which is the same as saying that (-1)^t≡ -1 (mod p^a).

Therefore, we have shown that a^t≡ -1 (mod p^a) when p is an odd prime and ord(p^a)a=2t.