Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
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". –  Arturo Magidin Jul 22 '11 at 19:23
    
Yes,you are right!My bad. –  Quixotic Jul 22 '11 at 19:27

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
+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
    
I got it now,and I think you actually answered my doubt.:) –  Quixotic Jul 22 '11 at 19:25

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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