2
$\begingroup$

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?

  • 0
    Yes,you are right!My bad.2011-07-22

2 Answers 2

5

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.

  • 0
    I got it now,and I think you actually answered my doubt.:)2011-07-22
1

$\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$

[1] Remainder Theorem