# Number of powers modulo prime

Is there any closed formula for the number of $i$-th powers modulo prime $p$ i.e. how many elements are there in set $\{1^i, \dots, p^i\}$ for arbitrary positive integer $i$ where powers are taken modulo $p$? I don't count zero since it's always present and no other power can result in zero, so we just need to add one to the number being discussed.

Here are the results for primes below $100$ and powers below $15$:

        1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16
2  ::  1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3  ::  2   1   2   1   2   1   2   1   2   1   2   1   2   1   2   1
5  ::  4   2   4   1   4   2   4   1   4   2   4   1   4   2   4   1
7  ::  6   3   2   3   6   1   6   3   2   3   6   1   6   3   2   3
11  ::  10  5   10  5   2   5   10  5   10  1   10  5   10  5   2   5
13  ::  12  6   4   3   12  2   12  3   4   6   12  1   12  6   4   3
17  ::  16  8   16  4   16  8   16  2   16  8   16  4   16  8   16  1
19  ::  18  9   6   9   18  3   18  9   2   9   18  3   18  9   6   9
23  ::  22  11  22  11  22  11  22  11  22  11  2   11  22  11  22  11
29  ::  28  14  28  7   28  14  4   7   28  14  28  7   28  2   28  7
31  ::  30  15  10  15  6   5   30  15  10  3   30  5   30  15  2   15
37  ::  36  18  12  9   36  6   36  9   4   18  36  3   36  18  12  9
41  ::  40  20  40  10  8   20  40  5   40  4   40  10  40  20  8   5
43  ::  42  21  14  21  42  7   6   21  14  21  42  7   42  3   14  21
47  ::  46  23  46  23  46  23  46  23  46  23  46  23  46  23  46  23
53  ::  52  26  52  13  52  26  52  13  52  26  52  13  4   26  52  13
59  ::  58  29  58  29  58  29  58  29  58  29  58  29  58  29  58  29
61  ::  60  30  20  15  12  10  60  15  20  6   60  5   60  30  4   15
67  ::  66  33  22  33  66  11  66  33  22  33  6   11  66  33  22  33
71  ::  70  35  70  35  14  35  10  35  70  7   70  35  70  5   14  35
73  ::  72  36  24  18  72  12  72  9   8   36  72  6   72  36  24  9
79  ::  78  39  26  39  78  13  78  39  26  39  78  13  6   39  26  39
83  ::  82  41  82  41  82  41  82  41  82  41  82  41  82  41  82  41
89  ::  88  44  88  22  88  44  88  11  88  44  8   22  88  44  88  11
97  ::  96  48  32  24  96  16  96  12  32  48  96  8   96  48  32  6


The numbers doesn't seem to show an obvious pattern so i wonder if there is any. But some patterns are present. If we take exponents of form $2^i$ then the number of $2^i$-powers seem to half till it's possible. What i mean can be illutstrated by the following example.

Consider $p = 73$. It's a well known result that there are exactly $\frac{p-1}{2}$ nonzero squares modulo any odd prime. For $p = 73$ we have $p - 1 = 72 = 2^3 \cdot 9$ and there are $\frac{p-1}{2} = 36~$ $~2$-powers and then the count halfes: we have $\frac{p-1}{2^2} = 18~$ $~2^2$-powers, $\frac{p-1}{2^3} = 9~$ $~2^3$-powers and since this number is odd we stop. For $i > 3$ i expect the number of $2^i$-powers to be equal to $9$.

The very same pattern though not very clear from the table above seems to be present for all given primes and all powers of the form $2^i$. Can we prove or dispove this pattern?

Thanks in advance :)

• Nice formula but i don't see yet how to prove it. Could you give any tips? Particularly where does gcd arrive from? – Igor Mar 19 '17 at 15:37
• Write your group $\mathbb{Z}/(p\mathbb{Z})^*$ as the set $\{g,g^2,\ldots,g^{p-1}\}$. What happens when you raise such elements to the $i$-th power? What is the cardinality of the new sets of exponents? – Jack D'Aurizio Mar 19 '17 at 15:40
• A-ha. I got it. Thank you very much! – Igor Mar 19 '17 at 15:50
• @JackD'Aurizio If you add your comment as an answer i'll vote for it. – Igor Mar 19 '17 at 15:52
• very kind of you. Done. – Jack D'Aurizio Mar 19 '17 at 15:55

## 1 Answer

It is well known that $\mathbb{Z}/(p\mathbb{Z})^*$ is a cyclic group with order $(p-1)$, hence it can be seen as $$\{g,g^2,\ldots, g^{p-1}\}$$ When we apply the map $x\mapsto x^i$ to such set, the new set of exponents has cardinality $$\frac{p-1}{\gcd(i,p-1)}$$ hence there are $1+\frac{p-1}{\gcd(i,p-1)}$ $i$-th powers in $\mathbb{Z}/(p\mathbb{Z})$.

• And again. Thank you very much. – Igor Mar 19 '17 at 15:58