8
$\begingroup$

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

$\endgroup$
  • 9
    $\begingroup$ 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? $\endgroup$ – Alex Apr 16 '17 at 3:59
  • 1
    $\begingroup$ Nobody else ever wrote $(C\equiv D \pmod E)^F$ before. What does it mean ? $\endgroup$ – DanielWainfleet Apr 16 '17 at 4:05
  • 1
    $\begingroup$ 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 math.stackexchange.com/a/2072179/19345.) $\endgroup$ – ruakh Apr 16 '17 at 21:07
  • 4
    $\begingroup$ @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. $\endgroup$ – leftaroundabout Apr 16 '17 at 21:48
  • 1
    $\begingroup$ 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$. $\endgroup$ – leftaroundabout Apr 16 '17 at 22:14
21
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What is the need of writing two answers that are almost same ? $\endgroup$ – A---B Apr 16 '17 at 16:22
  • $\begingroup$ 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. $\endgroup$ – Alex Apr 16 '17 at 17:26
  • $\begingroup$ @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. $\endgroup$ – Alex Apr 17 '17 at 6:22
  • $\begingroup$ 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 ? $\endgroup$ – A---B Apr 17 '17 at 7:53
  • $\begingroup$ The down votes under both of your answers are not by me, I can prove it. $\endgroup$ – A---B Apr 17 '17 at 7:54
22
$\begingroup$

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).$$

$\endgroup$
11
$\begingroup$

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.)

$\endgroup$
6
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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