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
    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.2011-07-22
  • 0
    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$.2011-07-22
  • 1
    "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".2011-07-22
  • 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
    +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$1$ as the remainder right? – 2011-07-22
  • 0
    @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$.2011-07-22
  • 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