- 9,490

- 6,502

This can also be seen by a simple long division or multiplication of polynomials: ##x^{n+1}-1=(x-1)\cdot (x^n+x^{n-1}+ \ldots + x+ 1)\,.##Alright, trying my hand at High School 3, and trying to get all my "i" dotted and "t" crossed this time. Doing it the long way - no shortcuts, or I'll end up kicked from the forum and sent back to pre-school! First part, for the sigma of prime decomposition

I - Define ##\sigma(x)## = sum of divisors of ##x##, including 1 and ##x##, for ##x \in N##

--------------------------------------------------------------------------------------------------------

II - Proof that if ##p## is prime, ##p > 1## and ##n>=1##, then ##\sigma(p^n) = (p^{(n+1)}-1)/(p-1)##

As ##p## is prime, ##p>1## and ##n>=1##, the divisors of ##p^n## are {##1, p, p^2, ..., p^n## }; the sum of these divisors form the sum of a geometric series:

##\sigma(p^n)## = ##1+p+p^2+...+p^n##

this series has ##a=1, rate=p, num=n+1##; as ##rate>1##, the series has ##sum=a*(rate^{num}-1)/(rate-1) = 1*(p^{(n+1)}-1)/(p-1)##, therefore

##\sigma(p^n) = (p^{(n+1)}-1)/(p-1)##

You could have saved all these deviations with divisors of ##z## by the use of the fundamental theorem of arithmetic: We always have ## z = \prod_i {p_i}^{r_i} ## for integers ##z## and so all the cases are only cases of different prime factors, resp. powers. The usual way - and I only add this for completion, not because your proof was wrong - is by induction.--------------------------------------------------------------------------------------------------------

III - Proof that if ##p## is a prime, ##p>1##, ##a \in N##, ##a>1##, ##n>=1##, and ##p## is not a factor of ##a##, then ##\sigma(p^n*a)=\sigma(p^n)*\sigma(a)##

(a) Define

##z = p^n*a##

(b) Define

P=set of divisors of ##p^n=\{1,p,p^2,...,p^n\}##

A=set of divisors of ##a = \{a_0,a_1,a_2,...,a_m\} ##, with ##a_0=1, a_m=a##

(c) For any ##u \in N, u>1##, such that ##u|z## and ##gcd(u, p^n)=1##; then ##u|a##; that's due to Euclid's Lemma; as ##u|a##, ##u \in A##, therefore ##u = a_j## for some ##j##, and ##u=p^0*a_j## for some j

(d) For any ##u \in N, u>1##, such that ##u|z## and ##gcd(u, p^n)=p^l## for some ##l>0## ; then necessarily ##u=p^l*v## for an integer ##v##, where ##gcd(v,p^n)=1##; then for some ##k_u \in N, k_u>0##:

##z=k_u*u=p^n*a##

##u=p^l*v##

##z/u=k_u=(p^n*a)/(p^l*v)##

##k_u=(p^n/p^l)*(a/v)##

as ##n>l## and ##k_u## is an integer and ##v## is not a multiple of ##p##, then necessarily ##a## is a multiple of ##v##, or ##v## is a divisor of ##a##:

##v|a##

therefore ##v \in A##, what means ##v=a_j## for some ##j##, and

##u=p^i*a_j## for some ##i,j##

(e) From (c) and (d), all divisors of z have the form ##p^i*a_j## for some 0<=i<=n, 0<=j<=m.

(f) Therefore the sum of the divisors of z is

##\sigma(z)=\sum_i (\sum_j (p^i*a_j)) = \sum_i (p^i * (\sum_j a_j)) = \sum_i (p^i * \sigma(a)) = \sigma(a)*(\sum_i (p^i)) = \sigma(a)*\sigma(p^n)##

--------------------------------------------------------------------------------------------------------

IV - Proof that ## \sigma ( \prod_i {p_i}^{n_i} ) = \prod_i \sigma( {p_i}^{n_i} ) ## if each ##p_i## is a different prime ##p_i > 1## and ##n_i>=0, 1<=i<=m##

(a) Define

##z = z_1##

## z_1 = \prod_i {p_i}^{n_i}, i>=1, ## that is ## z_1 = {p_1}^{n_1} * z_2##

## z_2 = \prod_i {p_i}^{n_i}, i>=2, ## that is ## z_2 = {p_2}^{n_2} * z_3##

...

## z_{(m-1)} = \prod_i {p_i}^{n_i}, i>=m-1, ## that is ## z_{(m-1)} = p_{(m-1)}^{n_{(m-1)}} * z_m ##

## z_m = \prod_i {p_i}^{n_i}, i>=m, ## that is ## z_m = {p_m}^{n_m}##

then, as each ##p_i## is a different prime,

## \sigma(z_m) = \sigma({p_m}^{n_m})##

## \sigma(z_{(m-1)}) = \sigma( ({p_{(m-1)}}^{n_{(m-1)}} * z_m ) = \sigma(p_{(m-1)}^{n_{(m-1)}})*\sigma(p_m^{n_m}) ##

...

## \sigma(z_1) = \sigma(p_1^{n_1} * z_2) = \sigma({p_1}^{n_1})*\sigma(z_2) = \sigma({p_1}^{n_1})*...*\sigma({p_m}^{n_m}) = \prod_i \sigma( {p_i}^{n_i} )##

--------------------------------------------------------------------------------------------------------

V - Proof that ##\sigma( \prod_i {p_i}^{n_i} ) = \prod_i (p^{({n_{i}}+1)}-1)/(p-1)## if each ##p_i## is a different prime ##p_i > 1## and ##n_i>=0##, for ##1<=i<=m##

(a) Just substitute II in IV

VI - Result: if the prime factorization of ##z## is ## z = \prod_i {p_i}^{n_i} ##, then ## \sigma(z) = \prod_i (p^{({n_{i}}+1)}-1)/(p-1)##

The induction principle is as follows: prove that a statement ##A(n)## is true for some specific ##n=n_0##. Then we assume we would have proven it for all numbers up to ##n##. If we now can show, that ##A(n)## implies ##A(n+1)## then we are done, since we have shown a way how to start from ##n=n_0## and get all the way up to any ##n##.

In our case ##A(n) = \left[ \sigma\left( \prod_{i=1}^n p_i^{r_i}\right)= \prod_{i=1}^n \frac{p_i^{r_i +1}-1}{p_i-1}\right]## and ##n_0=1##.

The verification, that ##A(1)## is true, is your step II.

Now we assume, that ##A(n-1)## is true.

By your step III, the induction hypothesis ##A(n-1)##, and again step II we know, that

\begin{align*}

\sigma\left( \prod_{i=1}^n p_i^{r_i}\right) &= \sigma\left( \prod_{i=1}^{n-1} p_i^{r_i}\right) \cdot \sigma\left( p_n^{r_n} \right)\\

&=\prod_{i=1}^{n-1} \dfrac{p_i^{r_i +1}-1}{p_i-1} \cdot \dfrac{p^{r_n+1}-1}{p_n-1}\\

&= \prod_{i=1}^{n} \dfrac{p_i^{r_i +1}-1}{p_i-1}

\end{align*}

and the formula is proven.

Another way is simply count the divisors. This would have shortened your step III as well:

Every prime power ##p_i^{r_i}## contributes divisors ##1,p_i,\ldots ,p_i^{r_i}## and every divisor can be combined with all the other divisors to get another one. So we have as many divisors as there are combinations of ##(\,1,p_1,\ldots ,p_i^{r_1}\,) \times \ldots \times (\,1,p_n,\ldots ,p_i^{r_n}\,)##, which sum up to ##\prod_{i=1}^n\ \frac{p_i^{r_i +1}-1}{p_i-1}##.

This was the main task. Now you can calculate ##\sigma(a)-a## and ##\sigma(b)-b## if ##a,b## have the given form.