# Proving a theorem about remainders

I am not sure if the nomenclature is correct but my module says this to be the remainder theorem,

If a natural number $n$ is divided by a natural number $m$ and can be brought in the form: $$\frac{x \cdot (a^p)^q}{a^p-1}$$ such that $n=x \cdot (a^p)^q$ and $m=a^p-1\,$ where $x,a,p,q \in \mathbb{N}$ and $x \lt m$, then the remainder of the division of $n$ by $m$ is $x$.

This theorem is holds and I have used this in some problems, I was inquisitive about how probably we can prove this? I asked my instructor but according to him I don't need to be bothered about the proof but only concentrate on solving the problems. However I am rather not much convinced; could anybody explain me how we can prove this?

-
Since "The Remainder Theorem" usually refers to the polynomial remainder theorem (the remainder of dividing $p(x)$ by $x-a$ is $p(a)$), I changed the title of the question. –  Arturo Magidin Jul 22 '11 at 18:58
Yes,I certainly have another definition for remainder theorem which says,$(x \pm z)$%$y = (x$%$y \pm z$%$y)$ %$y$,where $a$% $b$ gives the remainder when $a$ is divided by $b$. –  Quixotic Jul 22 '11 at 19:22
"Definition" is not the appropriate term; we are talking about theorems that are 'refered to' by the label "Remainder Theorem". My point was simply that if you tell someone "the Remainder Theorem", they are unlikely to think about this one, but rather about one of the more common ones that are called "remainder theorem". –  Arturo Magidin Jul 22 '11 at 19:23
Yes,you are right!My bad. –  Quixotic Jul 22 '11 at 19:27

Note that if $m=a^p-1$, then $a^p \equiv 1 \pmod{m}$. Therefore, $(a^p)^q\equiv 1^q \equiv 1 \pmod{m}$, so $$n = x(a^p)^q \equiv x\pmod{m}.$$ Thus, the remainder of dividing $n$ by $m$ is the same as the remainder of dividing $x$ by $m$. Since we are assuming that $x$ is nonnegative (a natural number) and that $x\lt m$, then the remainder of dividing $x$ by $m$ is $x$ itself; thus, the remainder of dividing $n = x(a^p)^q$ by $m$ equals $x$, as claimed.
+1,Thanks,Arturo this proof really looks much simple,but I couldn't did it myself as I never knew for $(a^p)^q\equiv 1^q \equiv 1 \pmod{m}$,$x(a^p)^q \equiv x\pmod{m}$,where $x<m$ also holds,but I guess this because we have $1$ as the remainder right? –  Quixotic Jul 22 '11 at 19:18
@Debanjan: I cannot parse your comment. If $a\equiv b\pmod{m}$, then $a^k\equiv b^k\pmod{m}$. Since $(a^p)\equiv 1\pmod{m}$, then raising both sides to the $q$th power gives $(a^p)^q \equiv 1^q\pmod{m}$; since $1^q=1$, then this means $(a^p)^q\equiv 1\pmod{m}$. And if $a\equiv b\pmod{m}$, then $ac\equiv bc\pmod{m}$ for any $c$, so from $(a^p)^q\equiv 1\pmod{m}$. multiplying both sides of the congruence by $x$ gives $x(a^p)^q\equiv x\cdot 1 = x\pmod{m}$. This proves $n\equiv x\pmod{m}$ under the given hypothesis, which yields that they have the same remainder when divided by $m$. –  Arturo Magidin Jul 22 '11 at 19:21
$\begin{eqnarray}{\bf Hint}\qquad & &\rm c\ f(z) &\equiv&\rm\, c\ f(1) &\ \rm(mod\:\ z-1) &\rm\ \ \ \ \forall\:\ \ f(z)\in \mathbb Z[x]\:,\ \ by\ Remainder\ Theorem\ [1]\\ &\ \Rightarrow\ &\rm c\ \ z^{\:q}\:\ &\equiv&\rm\ c &\rm\ (mod\:\ z-1) &\rm\ \ for\ \ f(z) = z^q,\ q\in \mathbb N\\ &\ \Rightarrow\ &\rm c\ a^{pq} &\equiv&\rm\ c &\rm\ (mod\ a^p\!-\!1) &\rm\ \ for\quad\,\ z\, =\, a^p,\in \mathbb Z,\ p\in\Bbb N \end{eqnarray}$
$\rm i.e.\ \ a^p\equiv 1\ \Rightarrow\ c\ (a^p)^q\equiv\ c\cdot 1^q \equiv\ c$