1
$\begingroup$

The following is an idle question on powers modulo composites. I find it natural and have no clue how to answer it. I am a beginning undergraduate, please include as many details as possible.

Setting : Let $n$ be an odd square-free composite integer. The ring $\mathbb{Z}/n\mathbb{Z}$ is thus not a field, and has cardinality $n$.

Let $k$ be any fixed integer between $1$ and $n$. Consider the $n$ powers : $0^k, 1^k,\dots, (n-1)^k$.

Questions :

a) is there a way to count explicitly the number of distinct values mod $n$ of these powers as a function of $n$ and $k$? Or maybe from the list of prime factors of $n$ and $k$?

b) better yet, is there a way to compute those values?

Remark: For a related (yet different) question, if $n = p$ is prime and $k=p$, then $a^p = a$ mod $p$: this is just Fermat's little theorem.

$\endgroup$
5
  • $\begingroup$ If the base has gcd $d$ with $n$ we get at most $\frac{n}{d}$ possible residues. For that base. And of course parity of $k$ determines if $x$ and $-x$ as bases produce the same residue. $\endgroup$ Jul 26, 2021 at 14:24
  • 1
    $\begingroup$ And of course $k\bmod \varphi(n)$ matters more... $\endgroup$ Jul 26, 2021 at 15:06
  • 1
    $\begingroup$ There are many ways to add context; saying "idle curiousity" is actually an improvement. Even when no general method of attack is available, it is often worth doing some small examples, as this can expedite responses from Readers at a level you would appreciate. For a general method, one might expand your thought about using the prime factors (how would that help?). $\endgroup$
    – hardmath
    Jul 27, 2021 at 21:22
  • $\begingroup$ @Archie That can be done under context rewrites , but usually only when the question has been closed and the answers are "worth" rescuing (but in this case, I'd argue that a reopening occured so someone would have done it, maybe me if someone asked me to do so). I was not unhappy at the fact that the question was reopened, but that it reopened with no improvement. As it stands, I think the edits are short and beneficial , as they should be. The context isn't "formatting" , it's useful information that is demanded to place the question in the frame you suit it to be in, which means ... $\endgroup$ Jul 29, 2021 at 9:42
  • $\begingroup$ ... that the best person to supply context, is you. So we could do some changes : but we can't be lying on your behalf, so the context rewrites don't allow too much freedom (if I may say, very little). Either way, if your next few questions are phrased like this I cannot see too much trouble. If you feel that adding context is arbitrary, then kindly visit a chatroom like this one and ask for prompts on how to provide context for your questions. I wish you a good time on the site (side note : +1). $\endgroup$ Jul 29, 2021 at 9:45

1 Answer 1

5
$\begingroup$

In principle, the answer to $a$ is "yes" (but it's perhaps a bit complicated), and the answer to $b$ is "not really".

First, reduce this to a question of primes by studying $\mathbb{Z}/p\mathbb{Z}$ for each prime $p \mid n$, and then use the Chinese Remainder Theorem to recombine to $\mathbb{Z}/n\mathbb{Z}$.

Now for each $p$, consider the $k$-power map $f$ from the multiplicative subgroup $(\mathbb{Z}/p\mathbb{Z})^\times \longrightarrow (\mathbb{Z}/p\mathbb{Z})^\times$, given by $f(x) = x^k \bmod p$. This is a homomorphism, so to find the size of the image it suffices to find the size of the kernel.

This group is cyclic, so there is some $a$ such that $(\mathbb{Z}/p\mathbb{Z})^\times = \langle a \rangle$. The kernel of the map $f$ in terms of $a$ consists of those elements $a^n$ such that $a^{nk} \equiv 1 \bmod p$. This occurs exactly when $nk$ is a multiple of $\varphi(p) = (p-1)$ (Fermat's Little Theorem and Carmichael's Theorem). Thus the kernel of the map $f$ consists of elements $a^n$ such that $nk \equiv 0 \bmod (p-1)$, or $nk = \alpha (p-1)$ for some integer $\alpha$. We may assume $1 \leq n \leq p-1$, as each element of $(\mathbb{Z}/p\mathbb{Z})^\times$ is given by one such $a^n$.

If $\gcd(k, p-1) = 1$, then necessarily $(p-1) \mid n$, which implies that $n = (p-1)$. In this case the only $a^n$ such that $a^{nk} \equiv 1 \mod p$ is $a^{p-1} \equiv 1 \bmod p$. Thus the size of the kernel is $1$, and so the image has size $p-1$. All numbers mod $p$ are $k$th powers.

More generally, if $\gcd(k, p-1) = d$, then $f(a^{\frac{p-1}{d}}) = 1$, and this is also true of the $d$ powers of $a^{\frac{p-1}{d}}$ up to $a^{p-1}$. The size of the kernel is $d$, and thus the size of the image is $\frac{p-1}{d}$. (This completely misses which $\frac{p-1}{d}$ elements are in the image).

Thus to fully answer $(a)$, factor $n$ and compute $$ \prod_{p \mid n} \big(1 + \frac{p-1}{\gcd(k, p-1)}\big).$$ This is because the image in $(\mathbb{Z}/p\mathbb{Z})^\times$ has $\frac{p-1}{\gcd(k, p-1)}$ elements, and $0$ is in the image (giving $+ 1$). And then CRT gives the product.


For example: consider $n = 15$ and $k = 4$. Then $15 = 3 \cdot 5$. We have that $(3-1)/\gcd(4, 3-1) = 1$ and $(5-1)/\gcd(4, 5-1) = 1$. Thus the image should be of size $(1 + 1)(1 + 1) = 4$. And if we explicitly compute these elements, they are $0, 1, 6, 10$.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.