# what are linear divisors of integer powers?

I have been trying to prove that $n^4$ is eithere divisible by $5k$ or $5k+1$, couldn't help wonder if there is a more general theme to try later , namely if it is true that $n^m$ is divisble by at least one of the $mk , mk+1 , mk+2 , mk+3 , \cdots , mk+(m-1)$ or something similar?

-
@ShreevatsaR, k=3 does the job. –  Arjang Jun 12 '11 at 16:41
Oops, yes. Sorry. –  ShreevatsaR Jun 12 '11 at 17:26
@ShreevatsaR : the only reason i mentioned k=3 was that I too thought for n=2 there was no answer initially, but then the "or" part reminded me to think again. –  Arjang Jun 12 '11 at 17:35

There is a very nice answer to this question when $m+1$ is a prime number. In this case, $n^m$ is divisible by either $km$ or $km+1$ for some $k$. (Notice that this solves your first question when $m=4$)

So we look at $n^{p-1}$. Well, either $p$ divides $n$, or it doesn't. In the first case, we have that $kp|n$ with $k=1$. In the second case, by Fermat's little theorem, $$n^{p-1}\equiv 1\pmod{p}.$$ This means that $n^{p-1}=kp+1$ for some $k$, so that in particular $kp+1$ divides $n^{p-1}$.

Hope that helps,

-

I will post this as an answer, mostly since it is too long for a comment.

It is critical in mathematics to state questions precisely. Interestingly enough, the same need not apply to proofs. In many settings, conveying the idea of the proof may be enough.

So what does "$n^4$ is divisible by $5k$ or $5k+1$" mean? What is $k$?

Chandru, from the link he gave, interprets the question to mean "$n^4$ is either of the form $5k$ or of the form $5k+1$." This is a way of saying what, in more modern language, would be expressed by writing that either $n^4 \equiv 0 \pmod{5}$ or $n^4 \equiv 1 \pmod{5}$.

Proving that this is true is easy. Imagine dividing $n$ by $5$. The remainder is $0$, $1$, $2$, $3$, or $4$. Now we need to find, in each of these cases, the remainder when $n^4$ is divided by $5$. This is easy by using basic properties of congruences.

But even if we know nothing about congruences, we can solve the problem because of our familiarity with the decimal system. We will be taking a fourth power, and $(-a)^4=a^4$. So we need only worry about $n^4$ for $n \ge 0$.

Look at the last digit of $n^4$ for $n=0$, $1$, $2$, and so on up to $9$. We get the pattern $0$, $1$, $6$, $1$, $6$, $1$, $6$, $1$, $6$, $1$. And if we continue, looking at $10^4$, $11^4$, and so on, the pattern obviously repeats.

When the last digit of $n^4$ is $0$, the number $n^4$ is divisible by $5$, that is, is of the form $5k+1$. When the last digit of $n^4$ is $1$, $n^4$ leaves a remainder of $1$ on division by $5$, so is of the form $5k+1$. This is also the case when the last digit of $n^4$ is $6$, for in this case also $n^4$ is $1$ more than a multiple of $5$.

We could use fancier tools to tackle the problem. Here is a nice result, called Fermat's (little) Theorem.

Let $p$ be prime, and let $a$ be an integer not divisible by $p$. Then $$a^{p-1}\equiv 1 \pmod{p}$$ To apply this to our problem, let $p=5$. If $a$ is divisible by $5$, then clearly $a^4$ is divisible by $5$. In all other cases, use Fermat's Theorem to conclude that $a^4 \equiv 1 \pmod{5}$, which means that the remainder when $a^4$ is divided by $5$ is $1$, which means that $a^4$ is of the form $5k+1$.

Your question: You asked a question that could be interpreted as being about the "shape" of $n^m$ in general. When the power $m$ is $1$ more than a prime, there is very useful information contained in Fermat's Theorem. There is also an important generalization due to Euler that you could easily track down by reading about Fermat's Theorem. Every beginning Number Theory book has the details.

A possible exploration: All of the above stuff has nothing to do with the phrase "linear divisors of integer powers." We have not been examining the divisors of $n^4$, only $n^4$ itself. A bit of thought will show that numbers of every shape whatsoever can divide $n^4$, if you put no restrictions on $n$.

Even with a simple example like $2^4$, the divisors are $1$, $2$, $4$, $8$, and $16$. Note that if you divide these by $5$, all remainders except $0$ occur.

It could be interesting to explore the following question. For a given integer $a$, and a given prime $p$, what are the possible remainders when powers of $a$ (things of the shape $a^m$) are divided by $p$.

If you start looking at these things, with the help of a good Number Theory book and/or the Internet, you will bump into interesting things, like primitive roots.

Divisors of $n^2+1$: At a more advanced level in number theory, one can tackle questions about possible shapes of divisors of, for example, $n^2+1$, and related questions. List to yourself the divisors of $n^2+1$ for various $n$. You will find no numbers of the from $4k+3$. This is no accident, it can be proved in general. A lot is known the shape of divisors of $n^4+1$. But for this sort of question, powers higher than $2$ in general lead to very difficult problems.

For power $2$, more subtle facts of this kind can be proved when one looks at quadratic residues and non-residues.

-
+1 for detailed analysis and points on clarification of question, points which I even didn't realise, and I considered myself a zelot for making questions precise, thank you for your time. Will modify the question to be more precise thanks to you. –  Arjang Jun 13 '11 at 6:31
@Arjang: You will notice that the Fermat Theorem stuff mentioned in the various posts shows that the number itself has a certain shape. Of course, the number divides itself, but the Fermat Theorem says nothing directly about the shapes of divisors of $a^{p-1}$. These shapes could be essentially arbitrary if one makes the appropriate choice of $a$. –  André Nicolas Jun 13 '11 at 6:47

By Fermat's Little Theorem $\rm\: n^{p-1}\:$ has form $\rm\:p\:k\:$ or $\rm\:p\:k+1\:,\:$ so it has itself as a divisor of that form.
More generally $\rm\ gcd(n,m)= 1\ \Rightarrow\ n^{\lambda(m)}\equiv 1\ \ (mod\ m)\$ for $\rm\: \lambda(n)\:$ the Carmichael function.
Your last remark is always true: every integer on division by $\rm\:m\:$ has remainder $\rm\:0,1,\cdots$ or $\rm\:m-1\:.$