8

I came to realise after practising some modular arithmetic that:

$x$, $(x-1)$$\space$ are$\space$ co-prime$ \space$ $\wedge$ $\space$ $x$, $(x-1)$ $\in$ $\mathbb{N}$ $\implies$ $x^\alpha \mod (x-1)$ = $1$ : $\forall$ $\alpha$ $\in$ $\mathbb{N}$

What is the name for this theorem, and who first proved it?

If someone could review the rigor of my proof that would be helpful:

Let the hypothesis be denoted as '$p$': $x$, $(x-1)$$\space$ are$\space$ co-prime$ \space$ $\wedge$ $\space$ $x$, $(x-1)$ $\in$ $\mathbb{N}$

Let the conclusion be denoted as '$q$': $\forall$ $\alpha$ $\in$ $\mathbb{N}$, $\space$ $x^\alpha \mod (x-1)$ = $1$

$p$ $\implies$ $q$.

Direct Proof:

Take the theorem $(A)^n \mod m$ $\iff$ $(A\mod m)^n \mod m$ : $A$ $\in$ $\mathbb{Z}$,$\space$ $n$, $m$ $\in$ $\mathbb{N}$: $m$ $\neq$ $0$

Then, given $p$, if we were to take the modulo $(x-1)$ of$\space$ $x^\alpha$ : $\alpha$ $\in$ $\mathbb{N}$,

$x^\alpha \mod (x-1)$ $\iff$ $(x \mod (x-1))^\alpha \mod (x-1)$

Since $x$ $-$ $(x-1)$ = $1$ (Given $p$):

$(x \mod (x-1))^\alpha \mod (x-1)$ $\equiv$ $[1]^\alpha \mod (x-1)$

We know that, $\forall$$\alpha$ , $1^\alpha = 1$

Hence, $[1]^\alpha\mod (x-1)$ $\equiv$ $[1] \mod (x-1)$

So,$\space$ $x^\alpha \mod (x-1)$ $\equiv$ $[1]$

Hence, $q$.

$p \implies q$.

$QED$.

Alex Boyle
  • 135
  • 9
    Why do you need the explicit hypothesis that $x$,$(x-1)$ are coprime? Two consecutive positive integers $x$,$(x-1)$ are coprime automatically, aren't they? – Alex Apr 16 '17 at 03:59
  • 1
    Nobody else ever wrote $(C\equiv D \pmod E)^F$ before. What does it mean ? – DanielWainfleet Apr 16 '17 at 04:05
  • 1
    Note that mathematicians don't use the concept of "taking the modulo", and don't use the notation "$a , \mathrm{mod} , b$". (I've written a bit about this at https://math.stackexchange.com/a/2072179/19345.) – ruakh Apr 16 '17 at 21:07
  • 4
    @ruakh well, mathematicians don't usually use $\operatorname{mod}$ as an infix operator $\mathbb{Z}\times\mathbb{Z}\to\mathbb{N}$ like programmers do, but I daresay it's something everybody should understand without too much difficulty. If actually used in a consistent manned, that is. The problem with this question is that it seems to mix both notions of modulo in a very confusing way. – leftaroundabout Apr 16 '17 at 21:48
  • @leftaroundabout From here on, is it by convention that I should stick to one notion solely when working on something? I'm new to modular arithmetic so thanks for this. – Alex Boyle Apr 16 '17 at 21:55
  • 1
    I suggest that as ruakh said, you stick to $a \equiv b \mod c$ when adressing a maths audience. It's equivalent to what a programmer would write as $a \operatorname{mod} c == b \operatorname{mod} c$. Certainly don't write $x\operatorname{mod} y \Leftrightarrow P$ – if the “result” of mod is supposed to be a logical proposition, then you must specify what you consider to hold modulo $y$. – leftaroundabout Apr 16 '17 at 22:14
  • It's called the Polynomial Remainder Theorem – Bill Dubuque Jul 01 '19 at 02:17

5 Answers5

21

Theorem: (reworded for readability) $ \ $ For any two positive integers $x$ and $\alpha$: $$ x^\alpha - 1 \quad\mbox{ is divisible by }\quad x - 1. $$

Proof: The difference $x^\alpha - 1$ can be factored as $$ x^\alpha - 1 = (x-1)(x^{\alpha-1}+x^{\alpha-2}+\ldots+x+1). $$ Q.E.D.

Alex
  • 4,873
  • 1
    What is the need of writing two answers that are almost same ? –  Apr 16 '17 at 16:22
  • The above answer is purely mathematical, while the other addresses the historical question "who first proved it?". The functionality allowing one user to write multiple answers exists for a reason. Remember to be nice and assume good intentions. – Alex Apr 16 '17 at 17:26
  • @A---B Comare these two statements: (A) "Difference of two squares always factors; difference of two cubes always factors in a similar manner; ditto for two biquadrates and higher powers." and (B) "All partial sums of a geometric series are integers iff all terms of such a series are integers." Do you honestly think (A) and (B) are the same? Granted, once we look at the formula for the sum of a geometric series, we begin to see a connection between (A) and (B) - but, to most students, these are two different ideas: (A) is about factoring a polynomial, while (B) is about summing a series. – Alex Apr 17 '17 at 06:22
  • Prove that $\sin x = \cos (\pi/2 - x) $ for $x \in [0,\pi/2]$. Now there are two ways to do this, one is to use the $\cos(A + B)$ and another is to observe a right angled triangle. Now by your logic both are different ideas and deserve two different answers right ? –  Apr 17 '17 at 07:53
  • The down votes under both of your answers are not by me, I can prove it. –  Apr 17 '17 at 07:54
21

First, let me compliment you on your enthusiasm and curiosity and ability to care about proofs.

Now the bad news. I'm afraid your theorem is trivial.

$$x= (x-1)+1 \equiv 1 \mod (x-1)\\ ⇒ x^{\alpha}\equiv 1^{\alpha} \equiv 1\mod (x-1).$$

Wrzlprmft
  • 5,718
fleablood
  • 124,253
11

Who first proved it?

From Wikipedia: Book IX, Proposition 35 of Euclid's Elements expresses the partial sum of a geometric series in terms of members of the series. It is equivalent to the modern formula $$ {x^\alpha-1\over x-1} = 1 + x + \ldots + x^{\alpha-1}. $$ For a geometric series with integer terms, the partial sum $\displaystyle{x^\alpha-1\over x-1}$ is an integer. (Yet another restatement of your theorem.)

Alex
  • 4,873
6

Modulo $x-1$ clearly $x$ is $1$. So all the powers of it are also $1$.

P Vanchinathan
  • 19,504
0

It doesn't have a name, I think. It is a consequence of $$x\equiv y\pmod z\implies \forall n\in \mathbb N\;[\;x^n\equiv y^n\pmod z\;]$$ which is shown by induction on $n$, by using the basic result that $$[x\equiv y \pmod z\land x'\equiv y' \pmod z]\implies xx'\equiv yy'\pmod z.$$

DanielWainfleet
  • 57,985