home | index | units | counting | geometry | algebra | trigonometry & functions | calculus analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

# Number Theory

God created the integers, all else is the work of man.
Leopold Kronecker (1823-1891)

### Related Links (Outside this Site)

Mathematics Enrichment  |  NRICH Prime Site  |  Plus Magazine  |  Math Mojo
What's Special About This Number?  by Erich Friedman of Stetson University.
Conjectures  at The Prime Puzzles & Problems Connection, by Carlos Rivera.
The Half-Totient Tree by Kevin Brown (1995-02-03)
Bézout's Identity for Gaussian Integers  by  Larry Freeman.
Arithmetic Progressions of Three Squares  by  Keith Conrad.

## Arithmetic  and  Number  Theory

dottcomguy00 (2001-03-21)
Is 1 a prime number?     (Modern A000040  vs. obsolete A008578.)

No, 1 is not prime.  This fact turns out to be more than a mere "technicality":

The modern definition of primality is that "a prime number is a positive integer with exactly two positive divisors". However, this may seem unconvincing (and/or arbitrary) by itself, until you stop to consider why we define things the way we do in mathematics, physics or other sciences. A relevant quote from Henri Poincaré has been given a superb concise English translation by John A. Wheeler, namely:

### Time is defined so that motion looks simple.

Good mathematical definitions are designed to make theorems simpler to state and easier to use.  We exclude "1" from the realm of prime numbers merely because almost all properties involving prime numbers, divisibility and factorizations would be more awkward to state if we didn't.

Consider just one essential example:  "Every positive number has a unique factorization into primes".  This would not be true if "1" was considered prime since you could add any number of "1" factors to (other) primes and obtain a product with the same value.

Even "1" has a unique factorization into primes, namely the "empty product" which contains no factors  and is therefore equal to the neutral element for multiplication.  (Why is an empty product equal to one?  Why is an empty sum equal to zero? Well, the same principle applies:  Any other definition would cripple Mathematical discourse with dubious "special cases".)

Historically, some number theorists did list "1" as a prime (e.g., D.N. Lehmer, the father of D.H. Lehmer, in 1914).  Some older textbooks also took this deprecated view.  This goes to show that it's not totally impossible to adopt other conventions...  However, such alternate definitions have proven to be far more awkward to use, and that's why we got rid of them:  1 is not prime.  Period.

 On 2004-06-14, Edgar Bonet wrote:       [edited summary] Regardless of what's currently accepted for positive integers, wouldn't it be more natural to call "prime" anything that does not have a non-trivial factor within a given set?   For example, the invertible polynomials [with real coefficients] are the nonzero constants (the polynomials of degree zero) which I'd like to call "prime", along with the polynomials of degree 1 and those polynomials of degree 2 which have no real roots. Edgar Bonet, Physicist

What you're describing are, in fact, the  irreducible  elements of a ring; those which cannot be expressed as a non-trivial product (a product of two factors being considered trivial if at least one of them has a reciprocal in the ring).

The concept of irreducibility is more generally applicable than the concept of  primality,  which is restricted to those rings where factorizations into irreducible elements are essentially unique  (which is to say that, in two such factorizations, every factor of one equals some factor of the other multiplied by an invertible element of the ring).  One example where factorizations are not unique is the set of complex numbers of the form  a + ibÖ5, where a and b are integers.  In this, the number  6  has two  unrelated  factorizations into irreducible factors:

6   =   2 ´ 3   =   (1 + iÖ5) (1 - iÖ5)

There are only nine discrete "grids" of complex numbers where factorizations are unique  (related to the nine Heegner numbers:  1, 2, 3, 7, 11, 19, 43, 67 and 163)  most notably the Gaussian integers and the Eisenstein integers.

In those cases where factorizations can be shown to be unique in the above sense, the term "prime" is often restricted to those irreducible elements which are not invertible and have some ad hoc additional feature which ensures factorization unicity.  (We keep as primes only positive numbers in the case of integers, or polynomials with leading coefficients equal to 1 in the case of polynomials.)  In this context, invertible elements are commonly called "units".  "Units" and "primes" play totally different roles in this general scheme.

+1 and -1 are units, they are not primes.

(2002-06-16)
Is "composite" the opposite of "prime" ?

No it's not, although it comes close.  Even in the realm of positive integers the number 1 is neither composite nor prime (see previous article).  The only natural integers which are neither prime nor composite are  0  and  1.

The term "irreducible" is favored to denote something that's not composite, but it's prudent to state exactly what you have in mind just before you use it for the first time in a speech or a text.  The ugly adjective "noncomposite" could be another option, which does not need prior explanations...

### "Rectangular Number"  is a deprectaed term :

In Number Theory,  the deprecated term  rectangular  was sometimes used as synonymous for  composite  in the above sense.

However,  Rectangular numbers  were also sometimes understood to denote  products of two  consecutive  integers,  which were of special interest to the ancient,  along with their halves called  triangular numbers,  a term we still use for integers of the form  n(n-1)/2.

Anonymous query, via Google   (2004-11-05)
What two prime numbers add up to their product?

As each prime divides the sum of both, it must divide the other.  This is only possible if the two primes are equal to some number p.  The sum and the product being both equal to 2p, we must have   p = 2.

2 + 2   =   2 ´ 2

(2002-06-14)   Gaussian Integers, Gaussian Primes, etc.
How does the concept of primality generalize beyond ordinary integers?

The so-called Gaussian integers  are complex numbers of the form  a+ib,  where a and b are integers.

Gauss showed that every Gaussian integer  uniquely  decomposes into a  unit  (one of the four invertible elements +1, -1, +i, -i ) and a product of irreducible elements from the  positive  quarter of the complex plane,  calling a Gaussian integer  x+iy  positive  when  -x < y < x+1 .

This is entirely analoguous to the  Fundamental Theorem of Arithmetic  whereby every ordinary integer is a product of an invertible unit  (namely,  its  sign;  +1 or -1)  and a unique decomposition of  positive  primes.

 1+i, 2+i, 2-i, 3, 3+2i, 3-2i, 4+i, 4-i, 5+2i, 5-2i, 6+i, 6-i, 5+4i, 5-4i, 7, 7+2i ...

Note that  1+i  is the only positive Gaussian prime whose conjugate is not a positive Gaussian prime as well  (since  1-i = (-i)(1+i)  isn't positive).

Ordinary prime integers are not necessarily prime among Gaussian integers.  Actually, a prime integer is a Gaussian prime if and only if it's congruent to 3 modulo 4.  In particular, 2 and 5 are not Gaussian primes:

2   =   -i (1+i)2           5   =   (2+i) (2-i)

Note that the above factorization of 2  (involving the "unit" -i)  is indeed the proper "unique" one, since the more obvious factorization  (1+i)(1-i)  uses a Gaussian integer which is not positive in the above sense...

AlisonWonder (2002-06-23)
How do you find the lowest common multiple (LCM)
of 3, 7, 24, 86, 125 and 214 ?

Small numbers like these are easily factored into primes:

3 and 7 are prime.  24 is 23´3.  86 is 2´43.  125 is 53.  214 is 2´107.

The factorization of their least common multiple (LCM) is obtained by using for each prime the highest exponent that appears in each of the above factorizations.  The result is, therefore:

LCM ( 3, 7, 24, 86, 125, 214 )   =   23 ´ 3 ´ 53 ´ 7 ´ 43 ´ 107   =   96621000

Factoring large numbers is often very difficult, so it's not a realistic option.  (In fact some modern schemes in public key cryptography do rely on the fact that it's difficult to retrieve two large prime numbers from their product.)

To find the least common multiple (LCM) of  two  large numbers,  compute their greatest common divisor (GCD) using Euclid's algorithm (or related algorithms that are similarly efficient).  You may then use the relation:

LCM(a,b)   =   ( a ´ b ) / GCD(a,b)

Given huge numbers like:

```       a = 2562047788015215500854906332309589561
b = 6795454494268282920431565661684282819```

The above formula allows you to "easily" compute the LCM of a and b:

```15669251240038298262232125175172002594731206081193527869
```
Note:   The above numbers (a and b) are not random ones.
They are both products of two very special 19-digit prime numbers...
HINT: Their GCD is 1111111111111111111 and the other factors are of a similar nature (in nondecimal bases of numeration).
vorobya (Alexey Vorobyov. 2002-10-18)   Aurifeuillian Factorizations
Prove that   n4 + 4   is composite (i.e., not prime) for all  n > 1

Well,   n4 + 4   =   (n2 - 2n + 2) (n2 + 2n + 2)   is a proper factorization,  since the smaller of the two factors is greater than  1  when  n > 1.

This type of factorization is often called  Aurifeuillian  (sometimes also spelled Aurifeuillean)  in honor of the French mathematician  [Léon François]  Antoine Aurifeuille  (1822-1882; X1841)  whose factorization methods were applied by Henri Le Lasseur de Ranzay  (an enthusiastic amateur who owned the  Château du Bois-Hue  in Saint-Joseph du Portricq, near Nantes).  Le Lasseur routinely shared his factorizations with Edouard Lucas (1842-1891)  and  Eugène Catalan (1814-1894; X1833).

Aurifeuille  once earned a living teaching high-school mathematics in Toulouse.  and authored three mathematical textbooks as  L. Aurifeuille :

• Cours de géométrie élémentaire,  with C. Richaud  (1847).
• Traité d'arithmétique,  with C. Dumont  (1859).
• Traité de géométrie élémentaire,  with C. Dumont  (1860).
Curiously,  Aurifeuille became quite famous as an illusionist under the stage name of  [Vicomte]  Alfred de Caston.  The great magician Robert-Houdin (1805-1871) was impressed by the way Aurifeuille used his wits in an act of mentalism.  Signing "de Caston", Aurifeuille authored several other books, related to "magic" or not, including:  Tartuffe Spirite (1866), Les vendeurs de Bonne Aventure (1866), La Turquie en 1873 (1874).  His masterpiece is still in printLes marchands de miracles: Histoire de la superstition humaine (1864).

The self-styled "vicomte" Alfred de Caston claimed to be a native of America.  He once lived in Turkey where he became editor-in-chief of the  Revue de Constantinople  in 1875-1876.  According to the records at Polytechnique  (which he entered in 1841)  Antoine Aurifeuille was born in Toulouse (France) on March 9, 1822  to an unwed mother of unspecified means of support, Jeanne Andrée Aurifeuille, living 26 place Mage  (a nice part of Toulouse)...  He joined a French writers guild:  La société des gens de lettres  (founded in 1838).

The attached caricature of Antoine Aurifeuille / Alfred de Caston  (provided by Ian Keable on 2012-02-12)  appeared in the French magazine  L'Escamoteur  (45, march-april 1954)  next to the photograph that inspired it.  The military description of Aurifeuille (1841) was:  Cheveux bruns.  Front découvert.  Nez épaté.  Yeux bruns.  Bouche moyenne.  Menton rond.  Visage ovale.  Taille: 171 cm.

Here are some algebraic factorizations, among many others :

 a2 - b2 = ( a - b )  ( a + b ) a3 - b3 = ( a - b )  ( a2 + ab + b2 ) a3 + b3 = ( a + b )  ( a2 - ab + b2 ) ( 2 a2 ) 2  +  b4 = ( 2 a2 - 2ab + b2 )  ( 2 a2 + 2ab + b2 ) ( 3 a2 ) 3  +  b6 = ( 3 a2 - 3ab + b2 )  ( 3 a2 + b2 )  ( 3 a2 + 3ab + b2 ) ( 5 a2 ) 5  -  b10 = ( 5 a2 - b2 )  ( 25 a4 - 25 a3 b + 15 a2 b2 - 5 a b3 + b4 ) ( 25 a4 + 25 a3 b + 15 a2 b2 + 5 a b3 + b4 )

In particular, with  b = 1,  two of the above relations can be used to break up  22(2n+1) +1   and  33(2n+1) +1  into several "nearly equal" factors :

 22(2n+1)  + 1   = (22n+1 - 2n+1 + 1)  (22n+1 + 2n+1 + 1) 33(2n+1)  + 1   = (32n+1 - 3n+1 + 1)  (32n+1 + 1)  (32n+1 + 3n+1 + 1)

In 1871, Aurifeuille himself used the first of those equations  (with n = 14)  to obtain immediately the following celebrated factorization:

258 + 1   =   536838145 . 536903681

The second number is prime.  The first one factors as   5 . 107367629

That same factorization had been  painstakingly  obtained by the retired Parisian mathematician  Fortuné Landry (1798-1895)  after casting out the factor  5.  Summarizing his factorizations in 1869, Landry wrote:

None of the numerous factorizations of the numbers  2n ± 1 gave as much trouble and labor as that of  258 + 1

This number is divisible by 5; if we remove this factor, we obtain a number of 17 digits whose factors have 9 digits each.  If we lose this result, we shall lack the patience and courage to repeat all calculations that we have made and it is possible that many years will pass before someone else will discover the factorization of  258 + 1

On July 12, 1880, Landry was 82 years old.  He earned a permanent spot in the history of numbers by presenting his factorization of the sixth Fermat number, without explaining how he did it  (there's no Aurifeuillian shortcut):

F6   =   2 64 + 1   =   274177 . 67280421310721

How was F6 factored?   by  Hugh C. Williams  (1993)
Cunningham Numbers by Tim Morrow   |   Aurifeuillian Factorizations (MersenneForum)
Another amateur interested in such things:  Charles Henry Gauss (1845-1913)  grandson of Carl Gauss.

Video :  (a+b)2 - (a+b)2  =  4 ab   Area of a Triangle  by  Presh Talwalkar  (MindYourDecisions, 2013-12-22).

(2006-02-05)   Euclid's Algorithm establishes Bézout's Lemma
Euclid's Algorithm gives the  greatest common divisor  d of two integers  p and q, and also yields two integers u and v such that  up + vq = d.

In the so-called Euclidean division of two positive integers  (the dividend  n  and  the  divisor  p)  the quotient  q  is the largest integer which goes p times into n.  This leaves a nonnegative remainder  r  less than p.  In other words:

n   =   p q  +  r       ( 0 £ r < p )

Euclid's Algorithm is an iterative procedure based on the remark that any common factor of n and p is also a common factor of p and r.  Until r vanishes, we may perform simpler and simpler divisions  where the divisor and remainder of one become the dividend and divisor of the next...  The last divisor (or last nonzero remainder) is then the greatest common divisor (GCD) of the original two numbers.  Here's how Euclid's algorithm yields 3 as the GCD of 5556 and 1233:

 5556 = 1233 . 4 + 624 1233 = 624 . 1 + 609 624 = 609 . 1 + 15 609 = 15 . 40 + 9 15 = 9 . 1 + 6 9 = 6 . 1 + 3 6 = 3 . 2 + 0

An important remark (expanded below) is that we may express the resulting greatest common divisor as a linear combination of the original two numbers by tracing back the steps in Euclid's algorithm  (proving  Bézout's lemma).

### Subtractive Version of Euclid's Algorithm  (anthyphairesis) :

The GCD of two integers may also be worked out by repeatedly replacing the larger of them by the  difference  of the two.  This simpler version of Euclid's algorithm is  less efficient  than the usual one described above  (using Euclidean division rather than mere subtraction)  but it can be convenient in proofs and other theoretical arguments (see below).

(2006-02-05)   Bézout's lemma  (or identity)  =  Bachet-Bézout theorem
The greatest common divisor (d) of two integers (p and q) is a linear combination of them:   d = up + vq  (where u and v are integers).
This very useful result is named after the French mathematician Etienne Bézout (1730-1783) although it was already well-known before his time.  In particular, it appears in the work of Claude Gaspar Bachet de Méziriac (1581-1638)  of  Bachet squares  fame (1624).

The canonical solution is obtained by tracing back the steps of Euclid's algorithm which compute the GCD of p and q.  With the above example  (p=5556, q=1233):

```3 =   (1)    9 +  (-1)   6 =   (1)    9 -     (  15 -      9)
=  (-1)   15 +   (2)   9 =  (-1)   15 +   2 ( 609 - 40. 15)
=   (2)  609 + (-81)  15 =   (2)  609 -  81 ( 624 -    609)
= (-81)  624 +  (83) 609 = (-81)  624 +  83 (1233 -    624)
=  (83) 1233 +(-164) 624 =  (83) 1233 - 164 (5556 - 4.1233)
=(-164) 5556 + (739) 1233
```

Note that  u  and  v  are not uniquely defined by  Bézout's identity, since:

u p  +  v q   =   (u+kq) p  +  (v-kp) q

However,  the pair obtained from the above procedure is well-defined:

### Bézout Coefficients and Bézout Function :   bezout(x,y)

A careful backtrack of Euclid's algorithm yields the definition of a  unique  function of two variables which gives the so-called  Bézout coefficients  (u and v)  without  the aforementioned ambiguity as the  simplest  possible solution.  Formally, such a function satisfies the following  nice  identity, unless |x|=|y|.

x bezout(x,y)  +  y bezout(y,x)   =   gcd(x,y)   ≥ 0

To make this hold in all cases, we'd have to put:   bezout (x, ±x) = ½ sign(x).  (For the sake of expediency,  we've retained  bezout (x, ±x) = 0   instead.)

 Forsaking that ad hoc exception, here's how to define  bezout  ona TI-92, TI-89 or Voyage 200. ```bezout(x,y) Func If x<0 : Return -bezout(-x,y) Local u,v,q,t abs(y)®y : 1®u : 0®v While y¹0   mod(x,y)®t   (x-t)/y®q   y®x : t®y   u-q*v®t : v®u : t®v EndWhile u : EndFunc```

Note that  bezout  is odd for one argument and even for the other:

bezout(-x,y)  =  - bezout(x,y)           bezout(x,-y)  =  bezout(x,y)

The above algorithm remains valid when the arguments of  bezout  are not integers  (because the same is true of the  mod  function which it uses).  Luckily, this is consistent with the generalized GCD function presented in the next article.

On Hewlett-Packard calculators  (HP-49g+, HP-50g)  the above  bezout  function for integers can simply be given the following definition:

«  IEGCD   ROT   DROP2  »

The acronym  IEGCD  (probably)  stands for  Integer Euclid Greatest Common Divisor  [ Algorithm ]  which gives a clue that the result is indeed precisely what the above describes  However, the terse wording of HP's technical documentation would, by itself, merely tell that the above three-instruction program yields what we need  modulo y.

BUG REPORT:   At least for versions 2.15 and below (2009) of the HP firmware, the  IEGCD  function requires the calculator to be set to  radians mode,  although angle measurements are utterly irrelevant.

### Bézout's Lemma in the Language of  Rings and Ideals :

 m  +  n     =     GCD(m,n)

The above expression may serve as a good introduction to the universally accepted convention introduced by  Hermann Minkowski (1864-1909)  whereby an operator defined for two elements is also defined when either formal operand is a  set  of such elements  (or when both are).  The result is then the set of all possible operations between an element from the first formal operand and an element from the second one.  Those things are called  Minkowski sumsMinkowski products  or  Minkowski operations.

Thus,  n   is the set of all multiples of the integer  n.  Likewise,  he sum on the left-hand-side is the set of all sums where one  addend  is a multiple of  m  and the other is a multiple of  n.  Bézout's lemma  states that those sums are precisely the multiples of the  greatest common divisor  of  m  and  n.

(2007-05-07)   GCD of two fractions... or two commensurable numbers
Extending the definition of a GCD beyond the realm of integers.

The  greatest common divisor  (GCD)  normally defined among integers (as computed by Euclid's algorithm) has two fundamental properties:

• gcd ( xp , xq )   =   x gcd(p,q)
• x / gcd(x,y)   and   y / gcd(x,y)   are two coprime  integers

Both properties are retained by defining the GCD of two fractions as the GCD of their numerators divided by the LCM of their denominators.  Software packages which support exact  rational arithmetic  (in advanced handheld calculators and elsewhere)  normally use this definition to extend the range of their GCD function beyond integers.  Rightly so...

gcd ( 2/3 , 1/2 )   =   1/6

This allows the GCD of two commensurable numbers to be defined as well:  Two real numbers are commensurable iff they are proportional to two integers;  Their GCD is simply the GCD of those integers multiplied by the common scaling factor.

gcd ( 2p/3 , p/2 )   =   p/6

The GCD of two numbers that are  not  commensurable is best defined to be  zero.  This makes the second fundamental property listed above  fail gracefully  (as it would entail  forbidden  divisions by zero).  With this convention, the celebrated  irrationality of  Ö2  can be stated compactly.  So can the epitaph of Roger Apéry  (the irrationality of Apéry's constant).

gcd ( 1 , Ö2 )   =   0
gcd ( 1 , z(3) )   =   0

clue  of the incommensurability of two numbers  x  and  y  may take the form of a small upper bound on their GCD.  Something like:

gcd ( x , y )   <   e = 10-100

Otisbink (2002-04-02)   Linear Diophantine Equations
How can I find integer solutions of a linear equation?
For example, (1,4) and (3,1) are integer solutions of   3x + 2y = 11.
How about a harder one like   1024 x - 15625 y  =  8404 ?

There are infinitely many integer solutions of   3x + 2y = 11  (two of them in  positive  integers).  They can be indexed by an integer  n Î  :

xn   =   1  +  2 n
yn   =   4  -  3 n

Any such equation whose unknown variables are required to be integers is called a  Diophantine equation  (as they were much studied by  Diophantus of Alexandria,  who died at the age of 84 around AD 284).  Here's how to solve for  x  and  y  any  linear  Diophantine equation,  like:

ax  +  by   =   c

First, compute the Greatest Common Divisor (GCD)  d  of  a  and  b,  using Euclid's Algorithm.  In the process, you will obtain two integers u and v such that  au + bv = d  (as explained above,  the existence such a pair of integers is a result commonly known as Bezout's lemma).

We have   a = da'   and   b = db' , where a' and b' are relatively prime.

Since the RHS of the equation is divisible by d, the LHS must be also. Therefore, d must divide c, or else the equation has no integer solutions. Let's assume, then, that  c  is equal to  dc'.  Using the above expression for d, the original equation  [divided by d]  may be rewritten as follows:

a' x + b' y   =   (a' u + b' v) c'       or       a' (x-uc') + b' (y-vc')   = 0

Therefore, b' divides the product a' (x-uc'). Since b' and a' are coprime, b' must divide (x-uc').  In other words, there exists an integer k such that x is given by the first equation of the following pair.  The second equation,  giving y,  is obtained by substituting that value of x in the original equation:

x   =   u c' + k b'
y   =   v c' - k a'

All solutions are thus explicitely given in terms of an arbitrary integer  k

In the proposed example,  a = 1024,  b = -15625,  c = 8404.  So, we have:

d = gcd(a,b) = 1     therefore  a' = a ,   b' = b ,   c' = c
u = bezout (a,b) = -4776     and     v = bezout (b,a) = -313

The above gives all the integer solutions of   1024 x - 15625 y  =  8404   in terms of a single integer parameter  k :

x   =   u c' + k b'   =   -40137504 - 15625 k
y   =   v c' - k a'   =   -2630452 - 1024 k

To make the constants as small as possible, we introduce  n = -2569 - k.  This way we obtain  canonical  formulas where nonnegative solutions for  x  and  y  correspond to nonnegative values of the parameter  n:

x   =   3121 + 15625 n
y   =   204 + 1024 n

Indeed:   1024 ( 3121 + 15625 n )  -  15625 ( 204 + 1024 n )   =   8404

Before negative numbers became commonplace  (in the Renaissaonce)  most ancient mathematicians were ultimately interested only in  nonnegative  solutions to this type of puzzles.  To us,  this can be a disposed quickly at the end in the form of an afterthought  (as we did above).  To them,  it would have been a burden to devise a sequence of steps where greater number was never subtracted from a smaller one.

When devising  recreational  puzzles,  it can be amusing to engineer linear Diophantine equations which have only one positive solution.  To do so,  start with canonical solution formulas which clearl give negative solutions for any nonzero value of the parameter  n  and work your way backward to eliminate  n  and obtain a linear equation which encodes a unique pair of nonnegative integers.

(2006-02-03)   Pythagorean Triples   (Pythagorean Triplets)
Solutions, in coprime positive integers, to the equation   x2 + y2 = z2

Such integers  x,y,z  are the sides of a right triangle.  The smallest solution is common knowledge:  x=3, y=4, z=5.  It turns out that  all  coprime solutions are of the following form  (the special case v=1 was given by Archimedes).

( u2-v2 ) 2  +  (2uv) 2   =   ( u2+v2 ) 2

Proof :   x and y can't both be odd  (otherwise, the sum of their squares would be  2 modulo 4, which can't be a square).  So, one of them must be even.  WLG, we may thus assume that y is even.  Let  y = 2a :

4 a 2   =   (z+x) (z-x)

The positive integers ½(z+x) and ½(z-x) are coprime  (or else the sum and the difference, z and x, wouldn't be coprime).   As their product is a square  (a2)  both of them are.  So, there are two integers  u  and  v  such that:

z+x  =  2u2   and   z-x  =  2v2,   which implies   y2  =  (2uv)2

Conversely, the above yields coprime solutions whenever u and v are coprime, without being  both  odd...  Below are the  smallest  such coprime solutions  (arguably, the trivial solution  y = 0,  does belong here).

  x  y z 1 3 5 15 7 21 35 9 45 11 33 63 55 13 77 0 4 12 8 24 20 12 40 28 60 56 16 48 84 36 1 5 13 17 25 29 37 41 53 61 65 65 73 85 85

Babylonian clay tablets  featuring lists of such  Pythagorean triples  (not necessarily coprime)  rank among the earliest mathematics on record.

• A009003  Hypothenuse numbers:   5, 10, 13, 15, 17, 20, 25, 26, 29, 30, 34, 35, 37, 39, 40, 41, 45, 50, 51, 52, 53, 55, 58, 60, 61, 65, 68 ...
• A009177  Hypothenuses of more than one triplet:   25, 50, 65, 75, 85, 100, 125, 130, 145, 150, 169, 170, 175, 185, 195, 200, 205, 221 ...

4 nontrivial triangles have integer sides and hypothenuse 65  (resp. 85) :

65 2   =   63 +  16 2   =   60 +  25 2   =   56 +  33 2   =   52 +  39 2
85 2   =   84 +  13 2   =   77 +  36 2   =   75 +  40 2   =   68 +  51 2

1105 is the hypothenuse of 13 distinct nontrivial Pythagorean triplets:

1105 2   =   1104 +  47 2   =   1100 +  105 2   =   1092 +  169 2
=   1073 +  264 2   =   1071 +  272 2   =   1020 +  425 2
=   1001 +  468 2   =   975 +  520 2   =   952 +  561 2
=   943 +  576 2   =   884 +  663 2   =   855 +  700 2   =   817 +  744 2

 N 1 2 3,4 5,6,7 8,9 ... 13 14,15 ... 22 23, 24 ... 31 32, 33 ... 40 A088959 5 25 65 325 1105 5525 27625 32045

The numbers that are expressible in many ways as sums of two squares  (A016032)  enjoy an  unfair advantage  in the above record-breaking game.

All possible Pythagorean triples, visualized (15:55)  by  Grant Sanderson (3Blue1Brown, 2017-05-26).

(Joe of Ann Arbor, MI. 2000-10-24)
What numbers have exactly  6  proper divisors ?   [A proper divisor is a positive integer  less than  the dividend which divides evenly into it.]

Consider the factorization into primes of the number N = AaBbCc...

When it comes to counting the number of divisors (for the time being let's count both 1 and N as divisors), only the sequence of exponents a,b,c,... matters (not the sequence of prime factors A,B,C,...). To get a divisor of N you should pick one exponent for the first prime among the (a+1) integers from 0 to a, one exponent for the second prime among the (b+1) integers between 0 and b, etc.

So, the total number of positive divisors of N is (a+1)(b+1)(c+1)...

If you want the number N to have exactly 6 proper divisors (counting 1 but excluding itself) the product (a+1)(b+1)... should be equal to 7. As 7 is prime this means the product in question only has one factor, so that you must have a=6 and nothing else. The number in question must be the sixth power of a prime. The first of these are 64, 729, 15625, 117649, 1771561, 4826809 ... A030516.

It is worth pointing out that the term "proper divisor" may exclude 1 as well as N. If you use this convention, the product (a+1)(b+1)... should be equal to 8. This corresponds to only 3 possible alternatives:

1. N is the product of 3 distinct primes.
2. N is the product of a prime by the cube of another prime.
3. N is the seventh power of a prime.
There are a lot more solutions this time:
1. The first class of solutions starts with 2´3´5 = 30, 2´3´7= 42, 2´3´11=66, 2´5´7=70, 2´3´13=78, 2´3´17=102, 3´5´7=105, 2´5´11=110, 2´3´19=114, 2´3´23=138, etc.
2. The second class starts with 23´3=24, 23´5=40, 2´33=54, 23´7=56, 23´11=88, 23´13=104, 33´5=135, 23´17=136, etc.
3. The third class is the sequence of seventh powers of primes: 128, 2187, 78125, 823543, etc.
The combined list is therefore: 24, 30, 40, 42, 54, 56, 66, 70, 78, 88, 102, 104, 105, 110, 114, 128, 130, 135, 136, 138, 152, 154, 165, 170 ... A030626.

(On a related topic, you may want to exercise your programming talents by  efficiently  generating in increasing order the products of 3 distinct elements from a given list of increasing integers.)

(2010-01-25)  Perfect Squares
The only positive integers witn an  odd  number of positive divisors.

With the notations introduced in the previous section, the total number of the positive divisors of  N = AaBbCc...  is:   (1+a) (1+b) (1+c) ...

This product is  odd  only when  all  its factors are, which is to say that all multiplicities  (a, b, c...)  are  even.  This happens iff  N  is a perfect square.

Video :   Maths Puzzle: Back to Black  by  James Grime  (2012-01-08).

Anonymous query, via Google  (2010-10-09)  Product of all divisors
For what numbers is the product of all divisors a perfect square?

If  p  is a prime factor of  N,  then  N = pQ  where  Q  is coprime with  p  (k is the  multiplicity  of p in N).  Let  m  be the number of divisors of  Q.

The number of divisors of  N  is  d = (1+k) m.  Exactly  m  of those are divisible by  p  with any prescribed multiplicity between 0 and k.  Therefore, the multiplicity of  p  in the product of all the divisors of  N  is:

m.0 + m.1 + m.2 + ... + m.k   =   m k (k+1) / 2   =   kd / 2

The product of all the divisors of  N  is thus a perfect square if and only if all such quantities are  even,  which is to say that  kd  is a multiple of 4 for the multiplicity  k  of every prime factor of  N.

If d is odd  (which means that N is a perfect square)  then the above is only satisfied when every multiplicity  k  is a multiple of 4, which is to say that  N  itself is a fourth power.

If d is  singly even  (which happens when one prime factor has a multiplicity congruent to 1 modulo 4 while all the others have even multiplicities)  then the above condition fails for the factor with odd multiplicity.

When d is a multiple of 4, the above condition clearly holds.  This happens when N has at least two prime factors with odd multiplicities or one factor with multiplicity congruent to 3 modulo 4  (as k+1 is divisible by 4, so is d).

All told, the product of all the divisors of  N  is a perfect square if and only if one of the following three conditions holds:

• N is a fourth power.
• N has at least two prime factors with odd multiplicities.
• N has a prime factor with a multiplicity congruent to 3 modulo 4.

1, 6, 8, 10, 14, 15, 16, 21, 22, 24, 26, 27, 30, 33, 34, 35, 38, 39, 40, 42, 46,  51, 54, 55, 56, 57, 58, 60, 62, 65, 66, 69, 70, 72, 74, 77, 78, 81, 82, 84, 85, 86, 87, 88, 90, 91, 93, 94, 95, 96, 102, 104, 105, 106, 108, 110, 111, 114, 115, 118, 119, 120, 122, 123, 125, 126, 128, 129, 130 ...   (A048943)

Divisor Product  by  Eric W. Weisstein,  in MathWorld

(J.E. of Lubbock, TX. 2000-10-25)   Perfect Numbers
A perfect number is a number whose divisors add up to itself:  1+2+3=6 1+2+4+7+14=28.  After 6 and 28, what are the next perfect numbers?
The proper divisors of a positive integer used to be called aliquot parts or proper quotients.  These include unity and all other positive divisors of the integer, except itself.  It's often more convenient to consider all the positive divisors of a number.  The sum s(n) of all the divisors of n has the desirable property of being multiplicative (which is to say that s(pq) = s(p)s(q), whenever p and q are coprime).  A perfect number may thus (also) be defined as an integer n such that  s(n) = 2n.
The factorization into primes of any number n consists of relatively prime factors of the type pm (p is prime and m is its multiplicity in the factorization); s(n)/n is the product of the factors (pm+1-1)/(pm+1-p).  The integer n is a perfect number if and only if this product equals 2.

Only the first four perfect numbers (6, 28, 496 and 8128) were known to Nicomachus of Gerasa  (c.AD 60-120 ; Gerasa is now Jerash, Jordan).  Nicomachus discusses the topic in his  Arithmetike Eisagoge  ("Introduction to Arithmetic",  c. 100)  an influential work which includes multiplication tables and the earliest known use of  Arabic numerals  (Indian decimal numeration) outside of India.  Nichomachus was the first to deal with Arithmetic independently from geometry, but his work is far less rigorous than what Euclid had done 4 centuries earlier.  Some of his "results" are just guesses.  Wrong guesses tainted the study of perfect numbers for centuries!

Euler  proved that all even perfect numbers are of the form given by Euclid, namely:  2p-1(2p-1), provided (2p-1) is prime.  Such a prime number  (i.e., one unit less than a power of 2)  is known as a  Mersenne prime.

### Are there any  odd  perfect numbers?

Nobody knows...  Finding an odd perfect number, or showing that none exist, is one of the oldest  unsolved  mathematical problems.

I think an odd perfect number can be found.
René Descartes  (1638)

The existence of an odd perfect number
would be little short of a miracle
.
James Joseph Sylvester  (1888)

An odd perfect number would necessarily be congruent to 1, 9, 13 or 25 modulo 36  (Touchard, 1953)  and would have the following properties:

• No fewer than 300 decimal digits.  [BCR 1991]
• A prime factorization with only one odd exponent.
• At least three prime factors greater than 100.   [Iannucci 2000]
• At least two prime factors greater than 10000.   [Iannucci 1999]
• At least one prime factor greater than 108.   Jenkins had established a lower bounded of 107 in 2003.  The same method was used by Goto and Ohno in 2006 to improve the lower bound to 108.
• At least one  prime-power  greater than 1020.   [Cohen 1987]
• At least 9 different prime factors.  The number of different prime factors was first proved to be at least  4  by Benjamin Peirce in 1832  (The Mathematical Diary, 2, XIII, pp. 267-277)  and, independently, by V.A. Lebesgue (1844).  It was shown to be at least  8  by Chein (1979) and/or Hagis (1980).  Nielsen improved this to  9  in 2006.
• Multiplicities  whose sum has been shown to be  at least  29 by Sayers (1986), at least 37 by Iannucci and Sorli (2003) and at least 47 by Kevin G. Hare (2004).  Hare improved successively his own record to 69, 71, 73 and 75 in 2005  to introduce a new method but "not necessarily to extend this bound to the farthest extend possible".

An odd perfect number with k prime factors can't exceed 24k [Nielsen 2003].

MathWorld   |   OddPerfect.org by William Lipp (still under construction as of 2007-12-01)
Seminar by Oliver Knill (Dec. 2007)

(2000-10-25)  Mersenne Numbers  &  Mersenne Primes
The ongoing search for prime numbers of the form  2- 1

Marin Mersenne (1588-1648) was a Parisian friar who built around him an influential scientific circle, well before the official creation of the French Academy of Sciences (1666).  In 1644, Mersenne proposed a tentative list of the powers of 2 whose predecessors are prime...

In his honor,  the number  2n-1  is called the  nth  Mersenne number  (the zeroth Mersenne number is thus zero).  When a Mersenne number is  prime,  it's called a  Mersenne prime.  Mersenne primes are tied to  perfect numbers.

Fr. Mersenne's first two mistakes were to omit exponent  61  from his mysterious list and to include exponent  67,  which was shown to yield a composite Mersenne number by Edouard Lucas, around 1875  (well before Frank Nelson Cole (1861-1926) heroically factorized it, in 1903).

As of  January 2018,  only 50 Mersenne primes are known, corresponding to the following values of the exponent  p.  (These are necessarily prime, because if  d  divides  p  then  2d-1  divides  2p-1.)

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917...   (A000043)

The list is widely believed to be  infinite,  but this has yet to be proved.

In recent years  (since 1989)  the largest known prime has always been a Mersenne prime  (contrary to popular belief,  this wasn't always so).

The  16  largest  known  Mersenne primes were found by  GIMPS :
RankPrime NumberDigitsDiscovered byDate
50 ?2 77232917-1   23249425 Jonathan Pace 2018-01-03
49 ?2 74207281-1   22338618 Curtis Cooper 2016-01-07
48 ?2 57885161-1   17425170 Curtis Cooper 2013-01-25
47 ?2 43112609-1   12978189 Edson Smith, UCLA2008-08-23
46 ?2 42643801-1   12837064 Odd Magnar Strindmo2009-04-12
452 37156667-1   11185272 Hans-Michael Elvenich2008-09-06
442 32582657-1   9808358 Curtis Cooper, Steven Boone2006-09-04
432 30402457-1   9152051 Curtis Cooper, Steven Boone2005-12-05
422 25964951-1   7816230 Dr. Martin R. Nowak2005-02-18
412 24036583-1   7235733 Josh Findley2004-05-15
402 20996011-1   6320430 Michael Shafer2003-11-17
392 13466917-1   4053946 Michael Cameron2001-11-14
382 6972593-1   2098960 Nayan Hajratwala1999-06-01
372 3021377-1   909525 Roland Clarkson1998-01-27
362 2976221-1   895932 Gordon Spence1997-08-24
352 1398269-1   420921 Joël Armengaud1996-11-13

See www.mersenne.org  for the latest update on the search for Mersenne primes.

Therefore, only  50  perfect numbers  are known at this [updated] writing, including huge ones.  Here is the beginning of the list:

```6, 28, 496, 8128, 33550336, 8589869056, 137438691328,
2305843008139952128, 2658455991569831744654692615953842176```

Of these, the last two (n = 31 and 61 in the above formula) were respectively discovered by Leonhard Euler (1772) and Ivan Mikheevich Pervushin (37 digits, in 1883).

The following ones, corresponding to n=89 and n=107, were discovered by R.E. Powers in 1911 and 1914.  They have respectively 54 and 65 digits.  Before that, the value n=127 had been shown to give a Mersenne prime of 39 digits (and a perfect number of 77 digits) by Edouard Lucas (1842-1891) in 1875.  Lucas could only achieve this by designing an efficient test, which would be the basis of all subsequent efforts, computerized or not (the Lucas-Lehmer test).  Lucas' heroic record would not be broken until the advent of the modern computer. The next two numbers in the list, the 13th and 14th Mersenne primes, are much larger (corresponding to n=521 and n=607) and were both discovered the same day (January 30, 1952, around 22:00 PST and shortly before midnight) by Raphael Mitchel Robinson (1911-1995), at the dawn of the computer age.

There's an interesting tale about the later discovery of the 19th and 20th Mersenne primes (corresponding to exponents 4253 and 4423) by Hurwitz and Selfridge in 1961:  Because of the way the computer printout was stacked, Alexander Hurwitz read about the larger number a few seconds before the smaller one.  The fact that history has now recorded that the 19th Mersenne prime (n = 4253) never held the record as the largest known prime clearly indicates that what we mean by "known" [for now and in this context, at least] is "known to some human being".  Mathematical and other scientific facts may be gathered automatically, but they become actual knowledge only when someone is aware of them.  It's simply a question of what our current vocabulary means, and that meaning may evolve.  Students of philosophy may still have fun wondering if a falling tree makes a sound when nobody is around to hear it, but they are currently up against an anthropocentric majority opinion:  In the mid 20th century, we did not [yet?] acknowledge a record broken by a machine, if  nobody  was aware of it while it "held"...

Henry Dobb (2002-05-26 e-mail) confirms the above story, which he heard from John Selfridge himself around 1990, when Selfridge was a visiting professor of mathematics at Florida Atlantic University.

The above incident has set a standard which was recently put to the test:  The computation that proved  M74207281  to be prime was acually completed on September 17, 2015.  However, the original e-mail report was either lost or ignored and nobody noticed for almost four months.  The official discovery date is thus January 7, 2016.  This may well be the weakest part of the GIMPS project, since Curtis Cooper is on record as stating that e-mail notifications failed for all four of the record-breaking primes he was involved with!

The Prime Factors of Mersenne Numbers

(2009-04-27)   Multiperfect Numbers  &  Hemiperfect Numbers

The abundancy   a(n)  =  s-1 (n)  =  s(n) / n   of a  perfect number  is  2.
More generally, a number whose abundancy is an  integer  is variously called a  multiperfect number  (MPN)  or a  pluperfect number.  The competing locution  "multiply perfect"  (used as early as 1907 by R.D. Carmichael)  is not recommended  ("multiply" would rhyme with "triply", not "apply").  Multiperfect numbers whose abundancy is  greater than  2  are called  proper  multiperfect numbers.

The effort to chart them has been spearheaded by  Achim Flammenkamp.

In spite of mounting computational evidence that some of the lists tabulated below are complete, Walter Nissen points out that this need not be so, even for our tiny list of six  3-perfect numbers.  Indeed, if  W  was a  [ huge ]  odd perfect number,  then the abundancy of  2W  would be  a(2) ´ a(W) = 3.

Arguably, the existence of an  odd perfect number  is a top contender for the title of  "oldest unsolved mathematical problem"...

We conjecture that there are only finitely many integers of abundancy  x,  except when  x = 2  (but a huge surprise is not ruled out here).
1 2 3 s(n)/n Multiperfect Numbers  (MPN)   A007691 Count 1 1 6, 28, 496, 8128, 33550336, 8589869056, 137438691328 ... ¥ ? 120, 672, 523776, 459818240, 1476304896, 51001180160 6 30240, 32760, 2178540, 23569920, 45532800, 142990848, 1379454720, 43861478400, 66433720320, 153003540480, 403031236608, 704575228896, 181742883469056, ... 36 14182439040, 31998395520, 518666803200, 13661860101120, 30823866178560, 740344994887680, 796928461056000, 212517062615531520, 69357059049509038080, 87934476737668055040, 170206605192656148480, 1161492388333469337600, 1245087725796543283200, ... 65 154345556085770649600, 9186050031556349952000, 680489641226538823680000, 6205958672455589512937472000, 13297004660164711617331200000, 15229814702070563916152832000, 34111227434420791224041472000, 36669339708545656151565926400, 41254809330254618094796800000, 52693888533626064627302400000, 59023729003862626557345792000 ... 245 141310897947438348259849402738485523264343544818565120000 ... 516 ?

In 1925,  Paul Poulet (1887-1946)  reported the first two 8-perfect numbers; they're both multiples of  262  with 42 and 43 distinct prime factors, respectively.

As of 2010, the only known number  n = 2.5185... 101906  for which  s(n)/n = 11  is a monster of  246  prime factors, found by George F. Woltman on 2001-03-13:

2468 . 3140 . 566 . 749 . 1140 . 1331 . 1711 . 1912 . 239 . 297 . 3111 . 378 . 415 . 433 . 473 . 534 . 593 . 612 . 674 . 714 . 733 . 79 . 832 . 89 . 974 . 1014 . 1033 . 1093 . 1132 . 1273 . 1313 . 1372 . 1392 . 1492 . 151 . 1572 . 163 . 167 . 173 . 181 . 191 . 1932 . 197 . 199 . 2113 . 223 . 227 . 2292 . 239 . 251 . 257 . 263 . 2693 . 271 . 2812 . 293 . 3073 . 313 . 317 . 331 . 347 . 349 . 367 . 373 . 397 . 401 . 419 . 421 . 431 . 4432 . 449 . 457 . 461 . 467 . 491 . 4992 . 541 . 547 . 569 . 571 . 599 . 607 . 613 . 647 . 691 . 701 . 719 . 727 . 761 . 827 . 853 . 937 . 967 . 991 . 997 . 1013 . 1061 . 1087 . 1171 . 1213 . 1223 . 1231 . 1279 . 1381 . 1399 . 1433 . 1609 . 1613 . 1619 . 1723 . 1741 . 1783 . 1873 . 1933 . 1979 . 2081 . 2089 . 2221 . 2357 . 2551 . 2657 . 2671 . 2749 . 2791 . 2801 . 2803 . 3331 . 3433 . 4051 . 4177 . 4231 . 5581 . 5653 . 5839 . 6661 . 7237 . 7699 . 8081 . 8101 . 8269 . 8581 . 8941 . 10501 . 11833 . 12583 . 12941 . 13441 . 14281 . 15053 . 17929 . 19181 . 20809 . 21997 . 23063 . 23971 . 26399 . 26881 . 27061 . 28099 . 29251 . 32051 . 32059 . 32323 . 33347 . 33637 . 36373 . 38197 . 41617 . 51853 . 62011 . 67927 . 73547 . 77081 . 83233 . 92251 . 93253 . 124021 . 133387 . 141311 . 175433 . 248041 . 256471 . 262321 . 292561 . 338753 . 353641 . 441281 . 449653 . 509221 . 511801 . 540079 . 639083 . 696607 . 746023 . 922561 . 1095551 . 1401943 . 1412753 . 1428127 . 1984327 . 2556331 . 5112661 . 5714803 . 7450297 . 8334721 . 10715147 . 14091139 . 14092193 . 18739907 . 19270249 . 29866451 . 96656723 . 133338869 . 193707721 . 283763713 . 407865361 . 700116563 . 795217607 . 3035864933 . 3336809191 . 35061928679 . 143881112839 . 161969595577 . 287762225677 . 761838257287 . 840139875599 . 2031161085853 . 2454335007529 . 2765759031089 . 31280679788951 . 75364676329903 . 901563572369231 . 2169378653672701 . 4764764439424783 . 70321958644800017 . 79787519018560501 . 702022478271339803 . 1839633098314450447 . 165301473942399079669 . 604088623657497125653141 . 160014034995323841360748039 . 25922273669242462300441182317 . 15428152323948966909689390436420781 . 420391294797275951862132367930818883361 . 23735410086474640244277823338130677687887 . 628683935022908831926019116410056880219316806841500141982334538232031397827230330241

Here are other numbers which divide  twice  the sum of their divisors:

3/2 5/2 7/2 s(n)/n Hemiperfect Numbers  (HPN)   A159907 Count 2 1 24, 91963648, 10200236032 3 4320, 4680, 26208, 20427264, 197064960, 21857648640, 57575890944, 88898072401645056, 301183421949935616, 9083288595228991885541376, 22290964134962716779872256, 230361837156847526055247872, 3551746147589248994873004392448, 8716209461184471402733217906688, 90076051101488582786918337478656, 275517471462331149989751161880576, 8319263987369391948455878608398843904, 20415999472827819113761327282781159424, 3081634264657305632386843579602306072576, 93050102500349677040144591462063024482811904, 228350830852095014942603539620449439316967424. 21 8910720, 17428320, 8583644160, 57629644800, 206166804480, 1416963251404800, 15338300494970880, 6275163455171297280, 200286975596707184640, 215594611071909888000, 5997579964837140234240, 39887491844324122951680, 189478877946949032837120, 464993138593758319902720, 4577250484712348791603200, 314220801442981320248524800, 14048146725436554258960875520, 20270811496597107858493931520, 81703797123392614369698250752, 612078178502919543930287114158080, 939834592031480161274941547741184, 1502078523847443989273473166868480, 2306413471743588373372911017263104, 157127060125322787706213898932715520, 954799029953763034837845432097308672, 2343137147924117580221226004651180032, 11528505172715763556107234109992568639979520000. 27 17116004505600, 75462255348480000, 6219051710415667200, 14031414189615513600, 352444116692828160000, 835095457414213632000, 59485231752222033838080, 64031599488357236736000, 564178061132326319357952000, 1208818605469519237939200000, 1384528609279142174195712000, 3101020675856435565821952000, 3333576337140514195596902400   ... 117ormore 170974031122008628879954060917200710847692800, 1893010442758976546037991125738431754692198400, 54361481238923605327597493185154939181072384000, 251754911117461891901909334695193204308626636800, 1896011572527867940620729403187025422081379532800, 1949479690331253229796013159150974699442693734400   ... 303ormore

Thanks to  Michel Marcus  for contributing to the extensions of the above tables  [ 11/2 | 13/2 ].  Note that, if the  prime  2q-1  isn't a factor of  n, then:

(2q-1)  s-1 ( n (2q-1) )   =   2q s-1 (n)

Thus, if the abundancy of  n (2q-1)  happens to be  q,  then the abundancy of  n  is equal to  q-1/2.  This way, a few hemiperfect numbers are obtained from some multiperfect numbers.  For example, with  2q-1 = 5  the above applies to the three  3-perfect numbers  which are multiples of  5  (since none of them is a multiple of  25)  namely 120, 459818240 and 51001180160  and yields the three known numbers of abundancy  5/2,  namely:  24, 91963648 and 10200236032.

Hemiperfect numbers of abundancy  5/2, 7/2, 11/2, 13/2, 17/2... are likewise obtained from  some  multiperfect numbers of abundancy  3, 4, 6, 7, 9...

This doesn't work for  15/2  because  15  is not prime,  but  Michel Marcus  has observed  (2009-09-15)  that a different  transformation  can be used to obtain numbers of abundancy  15/2  from any known number  7n  of abundancy  7  when  n  is coprime with  7  and  19.  Indeed, for such a cofactor  n,  we have:

s-1 (n)   =   s-1 (7 n) / s-1 (7)   =   7 / (8/7)   =   72 / 8
Therefore,   s-1 (72 19 n)   =   s-1 (72 19)  72 / 8   =   15/2

One satisfactory cofactor is:    n   =   2121. 324. 57. 116. 135. 173. 23 . 292. 312. 43 . 47 . 61 . 67 . 79 . 83 . 103 . 109 . 1572. 233 . 281 . 313 . 331 . 373 . 827 . 1549 . 2833 . 8269 . 8387 . 8951 . 9293 . 37171 . 45319 . 391151 . 1824726041 . 768614336404564651 . 2305843009213693951

The above replacement of the partial factorization   7190   by   7191   is one example of what's known, in this context, as a  substitution.  Michel Marcus has used such substitutions extensively to unearth large numbers with simple abundancies...  Conversely, some nontrivial  substitutions  were discovered as a byproduct of that search.  The following example  (which transforms a number of abundancy 8  into a number of abundancy 15/2 )  was obtained by Marcus on 2009-09-28:

s-1 ( 115. 17 . 372. 43 . 67 . 79 / s-1 ( 114. 37 . 432. 792. 179 . 631 . 3221 )   =   16 / 15

A cofactor of that substitution  (coprime with 11, 17, 37, 43, 67, 79, 179, 631 and 3221)  which yields numbers of abundancies 8 and 15/2 (225 digits) is:

268 . 325 . 57 . 712 . 135 . 194 . 232 . 29 . 47 . 612 . 71 . 97 . 103 . 131 . 137 . 1512 . 1572 . 197 . 2112 . 313 . 421 . 439 . 547 . 709 . 769 . 811 . 827 . 853 . 877 . 911 . 1093 . 1621 . 8269 . 19993 . 36833 . 110563 . 178481 . 3985812 . 797161 . 32668561 . 16148168401 . 10052678938039

### Abundancies  15/2,  17/2,  19/2  and beyond...

Michel Marcus  first found  (the hard way)  a  97-digit integer of abundancy  15/2  on July 4, 2009.  He then found  many more,  including the following  89-digit number of abundancy  15/2,  discovered on August 15, 2009 :

12749472205565550032020636281352368036406720997031277595140988449695952806020854579200000
=   235. 320. 55. 76. 112. 132. 17 . 192. 23 . 29 . 312. 372. 41 . 61 . 67 . 73 . 83 . 109 . 127 . 137 . 263 . 331 . 409 . 547 . 1093 . 4733 . 36809 . 368089

As of 2010, the smallest known 9-perfect number is a 287-digit number  x  which is divisible by 17  only once  (it was discovered by  Fred W. Helenius  in 1995).  So, the number  n = x/17  (which has 286 digits)  is an example of a number of abundancy 17/2  (the smallest known one has 191 digits).

n   =   3.30181224610218582352934080494271949153807... 10 285
=   2104. 343. 59. 712. 116. 134. 194. 232. 29 . 314. 373. 412. 432. 472. 53 . 59 . 61 . 67 . 713. 73 . 792. 83 . 89 . 97 . 1032. 107 . 127 . 1312. 1372. 1512. 191 . 211 . 241 . 331 . 337 . 431 . 521 . 547 . 631 . 661 . 683 . 709 . 911 . 1093 . 1301 . 1723 . 2521 . 3067 . 3571 . 3851 . 5501 . 6829 . 6911 . 8647 . 17293 . 17351 . 29191 . 30941 . 45319 . 106681 . 110563 . 122921 . 152041 . 570461 . 16148168401

By contrast,  19  never  appears with multiplicity one  in any known 10-perfect number.  We don't know any number of abundancy 19/2 (yet).

Multiply Perfect Numbers by  Achim Flammenkamp  (Universität Bielefeld)
Multiperfect Numbers  by  Eric W. Weisstein   |   Abundancy Resources  by  Walter Nissen
Nombres tétraparfaits  by  Édouard Lucas (1842-1891), quoted (in French)  by  Charles-É. Jean.

(G. S. of Farley, IA. 2000-11-15)
How can a  power ,  like 1217,  be calculated without actually multiplying the whole thing out?   [ as in  12´12´12´12´12´12´ ... ]

There are at least  2  ways.  The second one applies beyond ordinary numbers.

### First way: Use a table of logarithms.

You may use a table of logarithm.  Such tables have been available at your local library since the early 1600's.  Find the common logarithm of 12 (1.0791812) and multiply by 17.  This gives you 18.3460804.  You then use the table backwards to find that 0.3460804 is the log of 2.2186, so that your result is about 2.2186´1018.

### Second way: Use repeated squaring.

To obtain an exact result without going through 16 multiplications, you may notice that an even exponent means squaring the result for an exponent that's only half as big  (so that you "pay" the cost of just one multiplication to halve the exponent instead of reducing it just by one as you do with the "naive" method).  What if the exponent is odd?  Well, you can reduce the problem to that of an even exponent at the cost of just one extra multiplication.  (Can't you?)

With exponent 17, squaring four times with just one "extra" multiplication will do the trick :

12 17   =   (((12 2 )2 )2 )2 ´ 12

In other words:

• 12 2 = 144,
• 144 2 = 20736,
• 20736 2 = 429981696,
• 4299811696 2 = 184884258895036416
Multiply this by 12 to obtain the answer:  12 17 = 2218611106740436992

In this case, the number of multiplications has only been reduced from 16 to 5  (and they were more complicated to perform).  However, when the exponent is very large, the improved method becomes  much  better.  Indispensable, in fact.

Number theorists often use the above approach to compute  an modulo n,  for  very  large values of the exponent  n.  With modular arithmetic, we don't have to deal with larger and larger results because, at each iteration, we only consider the remainder of the division by  m,  which remains less than  m.

(Steve of Somerville, MA. 2000-11-16)   Partition Function (A000041)
How many ways can the numbers 1 to 15 be added together to make 15?  Is there a formula for that calculation?

The technical term for what you're asking is the "number of partitions of 15", which is often called p(15).  A partition of n is a collection of positive integers (not necessarily distinct) whose sum equals n.

This has been studied at length by the best mathematical minds of all times, including the Indian genius S. Ramanujan (1887-1920)  who collaborated with J.H. Hardy (1877-1947) to come up with a  fantastic  exact formula for the partition function  p(n), as a sum [rounded to the nearest integer] whose number of terms is on the order of Ön.  You may read about this on pages 97-99 of  Littlewood's Miscellany  by  John E. Littlewood (1885-1977).

In 1936,  Rademacher  gave a formula for p(n) as a convergent series.

"On the partition function p(n)"  by  Hans Rademacher (1892-1969)
Proceedings of the London Mathematical Society, 43, pp. 241-254  (1938).

The number of partitions p(n) is the coefficient of xn in the expansion of

(1+x+x2+x3+...) (1+x2+x4+x6+...) (1+x3+x6+...) (1+x4+x8+...) (...) ...

This coefficient is indeed obtained by counting the number of ways there is to choose an exponent multiple of 1 from the first factor, a multiple of 2 from the second factor, a multiple of 3 from the third, etc. so these exponents add up to n.  This leads to the formula for the "generating function" of p(n) which was first given by Euler (1707-1783) as the reciprocal of the products of all factors (1-xn) where n ranges over the positive integers.  (See Encyclopedia Britannica.)

Among many other similar essays, we recommend a recent lecture by Ken Ono.   [ 10 years after we made that recommendation here, Ken Ono made big news on this very topic ! ]

There are 176 partitions of 15, namely: 15, 14+1, 13+2, 13+1+1, 12+3, 12+2+1, 12+1+1+1, 11+4, 11+3+1, 11+2+2, 11+2+1+1, 11+1+1+1+1, 10+5, 10+4+1, ... ... 2+1+1+1+1+1+1+1+1+1+1+1+1+1+1, 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1.

 n  p(n) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490

Here's a simple BASIC program that will compute the number p(n) of partitions of n as an array of dimension m (m>2). The array "a" is just temporary storage. The program is based on Euler's basic remark and merely computes the first m coefficients in the product of all the series (1+xu+x2u+x3u+ ...). (arrays "a" and "p" hold the coefficients of the resulting polynomials):

```INPUT m
DIM a(m),p(m)
FOR i = 0 TO m: p(i) = 1: NEXT i

FOR u = 2 TO m
FOR i = 0 TO m: a(i) = p(i): p(i) = 0: NEXT i
FOR j = 0 TO m STEP u
FOR k = j TO m
p(k) = p(k) + a(k-j)
NEXT k
NEXT j
NEXT u

REM At this point, p(n) is the number of partitions of n
REM (for any n between 0 and m).
```

The following program achieves the same result  much  faster !

```input m
dim p(m)
p(0) = 1

for i = 1 to m
j=1 : k=1 : s=0
while j>0
j = i-(3*k*k+k)\2
if j>=0 then s = s - (-1)^k*P(j)
j = i-(3*k*k-k)\2
if j>=0 then s = s - (-1)^k*P(j)
k = k+1
wend
p(i) = s
next i
```

The above relies on the connection of partitions to both types of  pentagonal numbers  (A000326 and A005449)  which also translates into a simple way to compute the Dirichlet inverse (A129667) of the partition-based multiplicative sequence which  enumerates distinct Abelian groups  (A000688).  All of this ultimately rests on the following (nice) statement proven by Euler...

Euler's Pentagonal Number Theorem :
 ¥ Õ n = 1
( 1 - x n )     =
 + ¥ å k = -¥
(-1)k  x (3k2+k) / 2

(2011-01-21)  Ken Ono's great  epilog  on the partition function.
 Ken Ono, 2011Emory UniversityPhoto by Carol Clark

10 years after I enthusiastically recommended a lecture of his in the above introduction, Ken Ono made headlines on this topic by giving a  formula  for the partition function!

Ono appears modestly as the last author of two papers just published by the  American Institute of Mathematics.  The references below give links to the whole papers, a video by Ono and links to the press releases and blogs that are helping break the news  (in chronological order).

L-adic Properties of the Partition Function (pdf)
by  Amanda Folsom, Zachary A. Kent, and Ken Ono   (21 January 2011)
That result was immediately given a shorter proof  by  Frank Calegari  (bef. 2011-01-27).

An Algebraic Formula for the Partition Function (pdf)
by  Jan Hendrik Brunier and Ken Ono   (21 January 2011)

A suprise dimension to adding and counting (video)
Lecture delivered on 2011-01-21 by  Ken Ono  (2011-01-27)

New math theories reveal the nature of numbers  PR by  Beverly Clark, Emory University  (2011-01-20)
New math theories reveal the nature of numbers  First reactions at Physorg.com forum  (2011-01-20)
Finite formula found for partition numbers   by  S.C. Kavassalis   (2011-01-20)
Sequence of partition numbers found to be fractal   by  Ktwop   (2011-01-21)
Euler's Partition Function Theory Finished   by  Soulskill   (2011-01-21)
Ken Ono cracks partition number mystery   by  Yuiop  on PhysicsForum   (2011-01-21)
Una nueva teoría matemática revela la naturaleza de los números  ABC/Ciencia, Madrid  (2011-01-21).
Algebraic Formula for Partition Numbers (News) & Archives...   by  Robin Whitty   (2011-01-22)
Ken Ono Leads Team in Recent Mathematical Discovery  by  Elizabeth Bruml  for  emorywheel.com   (2011-01-24)
Una nueva teoría matemática revela la naturaleza de los números  by  En Línea Directa  (2011-01-26)
Deep meaning in Ramanujan's Simple Pattern.    by  Jacon Aaron  (2011-01-27)
Euler's Legacy:  Mathematiker feiern Entdeckung in der Zahlentheorie.   (2011-01-27)

Video :   New Theories Reveal the Nature of Numbers  by  Ken Ono   (2011-01-27)

DrGerard (Gérard Michon from Los Angeles, CA. 2000-11-18)
Let M be the sequence   M0= 0, M1= 1, and  Mn+2 = Mn+1 - 2 Mn
0, 1, 1, -1, -3, -1, 5, 7, -3, -17, -11, 23, 45, -1, -91, -89, 93, 271, ...
The Binet formula for Mn is :   Mn = (2/Ö7) 2n/2 sin (n atan Ö7 )
Considering this sequence modulo 8, it's clear that Mn cannot be equal to 1 if n > 2.  Prove that Mn can't be equal to -1 if n > 13.

As advertised, looking at the sequence modulo 8  (0, 1, 1, 7, 5, 7, 5, 7, ...) we see it can't go back to +1.  To prove that M never returns to -1 either for  n>13  is more difficult.  We need a few preliminary results about sequences obeying a second-order linear recurrence relation:

### Lemma(s) :

If  U0 = 0,   U1 = 1,   and   Un+2 = A Un+1 + B Un   then, for any sequence V such that Vn+2 = A Vn+1 + B Vn   we have:

Vn   =   V0 Un+1 + (V1 - A V0 ) Un

(This is easily established by induction on n.)
In the special case where  Vn = Un+k+1  we obtain :

Un+k+1   =   Un+1 Uk+1 + B Un Uk

### Theorem :

With the notations introduced above, the following relation holds whenever  A Ù B = 1 (that is to say, when the integers A and B are coprime):

Up Ù Uq   =   | UpÙq |

The expression  x Ù y  denotes the greatest common divisor (GCD) of x and y  (also known as their highest common factor, HCF).

Proof (outline):   The case  p = q  is trivial.  We assume, WLG, that  p>q  and we leave it to the reader to prove, by induction on q, that  Uq+1 Ù Uq  =  1.  We use the above lemma with  n+k+1 = p  and  k = q :

 Up Ù Uq = ( Up-q Uq+1 + B Up-q-1 Uq ) Ù Uq   =   ( Up-q Uq+1 ) Ù Uq = Up-q Ù Uq

This parallels the founding relation   pÙq = (p-q)Ùq   of the subtractive version of Euclid's algorithm.  The conclusion is thus obtained by induction, from  U0 = 0.

This theorem shows that a term in the M sequence can only be a prime or a unit (±1) if its index is either prime or divisible only by indices corresponding to earlier units (±1) in the sequence.  Below 13 and besides  n = 1, the only such indices are 2, 3, 5, and 13.  We see  by inspection  that the pairwise products and the squares of these special indices do not correspond to a value of -1 for M.  From this, we deduce that the lowest index n above 13 corresponding to a value of  -1  cannot be composite.  It must be prime.

Now, consider the sequence modulo 1171.  Its period is 1170, which is divisible by 3, 5 and 13.  The preperiod is of length zero (which is to say that the two residues 0 and 1 occur again consecutively  1170 terms later).  Also, the only terms in the first period that are congruent to -1 correspond to the indices 3, 5 and 13.  This means that any index n for which M is equal to -1 must be of one of the following three forms (for some integer k):  1170 k + 3,  1170 k + 5,  or  1170 k + 13.  Each of these is divisible by 3, 5, or 13.  This implies that n cannot be prime, unless it's equal to 3, 5, or 13...  Therefore, the value -1 occurs only 3 times in the sequence M.

This proof is only convincing if you actually check 1170+2 terms of the sequence modulo 1171.  There are many moduli like 1171  (including  1991, 3513, 5855, 5973, 6377, 8197, 8971 ...)  for which the period of M is a multiple of 3´5´13 and all the indices of terms congruent to -1 are divisible by 3, 5, or 13...

 I first posted this problem on 2000-11-18 at the defunct "Answer Point" of ask.com, where it received no attention whatsoever.  The incentive which made me come up (finally!) with the above solution, on July 8, 2002, was provided by the interest the problem generated among the first math topics (2002-06-08) of the new AnswerPool.com board: Maiku, have you got the answer to DrGerard's "-1" question yet?  Working on it with a glass of Jack Daniels hasn't helped me one bit. [Coldfuse, 2002-06-10 on msn AnswerPoint]  I fear that the methods required are over my head.  [FlyingHellfish]. I've given it some thought, but I'm stuck.  [Maiku] I got lost really quickly.  [WiteoutKing] This one is a doozy!  [Coldfuse, 2002-07-02]  I have printed [this proof] for posterity [but] what's the significance of it all?   [Donaldekliros, 2002-07-13]

In any integer sequence which (like M) starts with 0 and 1 and obeys a second-order linear recurrence with coprime coefficients, a prime number can only occur at an index which is either prime or only divisible by another index where the sequence is ±1.  For example, Mersenne primes may only occur at  prime locations  [sic]  in the  Mersenne sequence  A000225.

Similarly, Fibonacci primes occur only at prime indices within the   Fibonacci sequence  A000045, with just one exception  (the number 3 occurs at index 4).

The sequence M itself happens to have the lowest [exponential] growth among such sequences  (we're ruling out 6 trivial cases with subexponential growth).  Heuristically, M is thus expected to be more densely populated with primes than any other sequence ot its kind.  The above result can be used to prove that there are only 9 composite indices  (4, 6, 8, 9, 10, 15, 25, 26, 65)  for which M is actually prime.  This makes it much easier to work out the sequence of all the indices n for which Mn is prime, namely:

4, 6, 7, 8, 9, 10, 11, 15, 17, 19, 23, 25, 26, 29, 31, 47, 53, 65, 67, 71, 73, 113, 127, 199, 257, 349, 421, 433, 449, 691, 761, 823, 991, 1237, 1277, 1399, 1531, 1571, 3461, 3697, 4933, 6199, 7351, 9551, 9719, 11681, 12037, 14629, 14951, 19079, 20327, 22549, 30517, 51511, 52813, 60923, 73943, 79687, 91249, 115321, 117017, 169493, 172411, 174413, 237053, 285631, 318751, 327433 ... (A101087)

(2009-06-29)   Primes in  standard Lucas sequences
A standard sequence has only finitely many primes of composite index.

Let's generalize the above result to any  Lucas sequence of the first kind with coprime coefficients  (which we may call a  standard Lucas sequence, for short).  By definition, such a sequence starts with 0,1 and obeys the following recurrence relation for two  coprime  integers  A  and  B :

U0 = 0,     U1 = 1,
Un+2   =   A Un+1 + B Un

This makes the above lemma and theorem hold.  We shall use the same approach as in the previous article to prove that the values -1 amd +1 appear only finitely many times  (the advertised result follows from that fact, as previously explained).

(2008-05-06)   sequence of bits  with strange statistics
On the number of perfect squares between two consecutive cubes.

Let's count the squares between  n3  (included)  and  (n+1)3  (excluded):

n3Perfect SquaresCount
001
11, 42
89, 16, 253
2736, 492
6464, 81, 100, 1214
125144, 169, 1963
216225, 256, 289. 3244
343361, 400, 441, 4844
512529, 576, 625, 6764
729729, 784, 841, 900, 9615
1000   1024, 1089, 1156, 1225, 1296   5

Thus, there are at least two perfect squares between two (positive) consecutive cubes.  For large values of  n,  there are many more, of course.  Let's see how many:  Within  k  consecutive numbers located around some large integer  m,  we would expect to find about  k / 2Öm  perfect squares.  There are  k = 3n2+3n+1  numbers between  m = n3  and the next cube, so we may expect to find roughly 1.5 Ön  perfect squares among these.  This is, in fact, an excellent estimate since the actual count is always one of the two integers which bracket that quantity...

So, by subtracting the  floor  of  1.5 Ön,  from our counts of the perfect squares  (1, 2, 3, 2, 4, 3, 4...)  we obtain a particular sequence of zeroes and ones:

1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0...  (A140074)

closed formula  for this  bit sequence  is easy to obtain:

 bn   = ( n3 + 3n2 + 3n ) 1/2 - n 3/2 +   1   - 3 n 1/2 2

This sequence of  pseudo-random  bits has particularly intriguing statistics.  Let's mention a few properties that have been observed by studying one million terms.  (Most of the following statements have yet to be formally proved.)

• 0 and 1 are equally likely.
• Two adjacent bits are equally likely to match or mismatch.
• If  j  is a nonzero number of positions between two bits,  then their values will match with probability  p(j).  The value of  p(1)  seems to be  2/3 and  p(j)  varies very slowly with  j  in what appears to be a long-period damped oscillation toward a limit which is (most probably) equal to 1/2.  The first minimum has a value of about  0.45  around  j = 400.
• Other more complicated short-range correlations exist which are not fully accounted for by the above main effect.  For example, the patterns 0011 and 1100 are very rare.

In spite of the many open questions thus raised, this sequence serves as an example of a "natural" pseudo-random sequence which unexpectedly fails to obey long-range randomness for  mysterious  reasons.

Let's draw a bold analogy with a fundamental open question:  The Riemann Hypothesis (RH) can be construed as a belief that the sequence of prime numbers lacks a certain type of long-range order.  I offer the above example as a stern warning that the opposing belief is tenable, in spite of current heuristic "evidence".  The fashionable temptation to  assume  that RH is true ought to be resisted...

(2007-12-02)   Binet's Formulas   (Euler c. 1730,  Binet 1843)
The n-th term in a sequence obeying a second-order recurrence.

For two given constants  A  and  B,  consider the sequences  V  which obey

Vn+2   =   A Vn+1 + B Vn

Those form a two-dimensional vector space, where each element is entirely determined by its "coordinates"  (V, V).

For example, the (first part of) the above lemma can be construed as expressing any such sequence  V  as a linear combination of the two linearly independent sequences of coordinates  (0,1)  and  (1,A).  If the first of those is dubbed  U,  the second one is simply the sequence whose  n-th  term is  Un+1

Now, consider the following sequence  W :

Wn   =   z n       where   z 2 = A z + B

The quadratic equation satisfied by  z  ensures that the sequence  W  belongs to the above vector space.  Usually, there are two distinct (complex) roots to that equation, yielding two linearly independent sequences of the above form, which can serve as a vector basis.  So, the n-th term of any sequence  V  is of the form:

Vn   =   x an  +  y bn       where   (z-a)(z-b)  =  z 2 - A z - B

In particular, for the sequence  U  (which starts with  U0 = 0  and  U1 = 1) :

 Un   = an - bn a - b

In the special case when  a = b   the above breaks down.  Instead, we have:

Un   =   n a n-1

Such explicit expressions are called  Binet formulas,  in honor of the influential French mathematician  Jacques Binet (1786-1856; X1804)  who succeeded Poisson as Professor of mechanics at  Polytechnique  in 1815.  (Binet had been a classmate of Fresnel and the coach of Babinet.)  The term applies especially to the case of  Fibonacci numbers  (A = B= 1) :

Fn   =   [ fn - (-f)-n ] / Ö5       where   f = (1+Ö5) / 2   =   1.61803...

 Jacques Binet That special case is certainly the most popular use of  Binet's formulas, but  all  such formulas are named after  Jacques Binet,  whether they pertain to the Fibonacci sequence or not.  Binet was apparently the first to explain the general formula in the way outlined above,  using what we would now call  abstract vectors  (this was a novel idea in 1843,  the very year when Hamilton invented quaternions,  since even  geometric  vectors weren't commonplace).  Famous for his algebraic generalizations,  Binet had been the first to describe the general rule for matrix multiplication, in 1812.

The general formulas predate  Binet  by more than a century.  They were known to  Abraham de Moivre (1667-1754)  and  Leonhard Euler ((1707-1783).  D'Alembert (1717-1783)  had even presented the degenerate case  (a = b)  as a limit of the nondegenerate one  (in a nonrigorous way, by modern standards).

Recall  that  any  sequence  V  obeying a second-order linear recurrence  ["degenerate" or not]  can be expressed in terms of the above  standard  sequence  U  (obeying the same recurrence and starting with 0 and 1) :

Vn   =   V0 Un+1 + (V1 - A V0 ) Un

Usage Note :   Any explicit formula for the n-th term of a sequence obeying a linear recurrence relation can be called a "Binet formula".  When the complex roots of the characteristic equation are not real, their powers can be expressed with trigonometric functions  (the sequence has then an oscillatory aspect examplified elsewhere).  Arguably, that usage extends beyond the second order, regardless of the scarcity of examples  (see A141385 for an example of a third-order Binet formula).

(2007-11-29)   Cassini's Identity   (1680)

If  U0 = 0,   U1 = 1,   and   Un+2 = A Un+1 + B Un   then:

Vn   =   Un2  -  Un+1 Un-1   =   (-B)n-1     for any positive integer  n

This relation is usually stated in the context of  Fibonacci numbers  (A=B=1) where it's known as  Cassini's identity.  It was discovered in 1680 by  Jean-Dominique Cassini (1625-1712)  and it has been rediscovered many times since, most notably by Robert Simson (1687-1768; pedal line)  in 1753.

Proof :   Using  V1 = 1,  the general case is established by induction on  n :

Vn+1   =   (A Un + B Un-1 ) Un+1  -  (A Un+1 + B Un ) Un   =   (-B) Vn

(2007-11-29)   d'Ocagne's Identity
A generalization of Cassini's Identity due to  Maurice d'Ocagne.

Un Um+1  -  Un+1 Um     =     (-B) Un-m       [ where  n ≥ m ]

Proof :   For a given value of  m, let's consider the following function of  i :

Wi   =   Um+i Um+1  -  Um+i+1 Um

As  W0 = 0,  the above lemma shows that  Wi = WUi  where the value  W1 = (-B)m  is obtained immediately from Cassini's Identity.

Curry's Paradox  by  Alexander Bogomolny

Philibert Maurice d'Ocagne du Plessis (1862-1938; X1880)   a.k.a. Pierre Delix, playwright.

(2007-11-30)   Catalan's Identity   (Eugène Catalan, 1879)
Another generalization of Cassini's Identity.

Un2  -  Un+m Un-m     =     (-B)n-m  Um2       [ where  n ≥ m ]

Like Cassini's Identity and d'Ocagne's identity, Catalan's Identity  is almost always stated  only  in the context of  Fibonacci numbers  (A=B=1).

Proof :   We'll apply Binet's formula to etablish the result when the two roots  a  and  b = (-B/a)  of the characteristic equation are distinct  (by continuity, this will also establish the result for the special case when they are equal).  To streamline notations, we prefer to deal with the sequence  Vn = (a-b) Un

Vn   =   an - (-B/a)n

Well, let's just evaluate   Vn2  -  Vn+m Vn-m     :

a2n  -  2 (-B)n  +  (-B/a)2n  -  { an+m - (-B/a)n+m }  { an-m - (-B/a)n-m }
=     -  2 (-B)n  +  (-B)n-m a2m  +  (-B)n+m / a2m
=     (-B)n-m  [ a2m  -  2 (-B)m  +  (-B/a)2m ]
=     (-B)n-m  Vm2

Kirk Guidry (2002-03-30; e-mail) Faulhaber's Formula
[...] For a given p, how do you derive a formula for the sum of the p-th powers of the first n integers?  I have seen formulas for up to p = 10, but I still have difficulties deriving the formula for p = 5...

The general formula you are after is sometimes called Faulhaber's Formula and I'll give it to you below... However, your question is not really about formulas but rather about the methods which may be used to obtain them. I'll give you two such methods. The first one is elementary and can easily be used to solve your original concern about the formula for the sum of fifth powers. The second method is not so elementary (it involves the concept of generating functions) but is much more powerful and can be used to establish the general formula, which involves  Bernoulli Numbers.

I still remember fondly the heroic elementary proof I devised for this very formula, at age 15 or 16, thus "discovering" this mysterious Bernoulli sequence, which I had never encountered before.
On 2002-12-24, Ben Orin wrote:     [edited text]
[...]  I recall reading a derivation of this formula in my calculus book (as the trepidation induced by my first encounter with the Bernoulli sequence serves to vivify).
I remember the dissatisfaction that ensued, and the prompt contrivance of the formula that would soon pacify me:

To sum the pth powers of the first n integers, note that this sum is a polynomial in n of degree p+1, which is thus fully specified by p+2 of its points.  Therefore, for each p, we may express the sum as a Lagrange interpolating polynomial.  For example:
 n p+2 { k } å m p   = å å m p Õ (n-j) / (k-j) m=1 k=1 m=1 j Î{1, 2 ... p+2}-{k}

Ben Orin
Ventura College Dept. of Mathematics

In the above expression, the chosen range for k and j (namely {1, 2, ... p+2}) is an arbitrary example.  As Ben points out, any set of p+2 points would do.  This approach would establish the formula for p=5, say, by summing up 7 polynomials of degree 6 (each expressed as a product of 6 linear functions of n).  It fails to highlight the relation to the Bernoulli sequence.

Factored expressions for small values of the exponent p.
p
 n å m p m=0
0n+1
1n (n+1) / 2
2n (n+1) (2n+1) / 6
3n2 (n+1)2 / 4
4n (n+1) (2n+1) (3n2+3n-1) / 30
5 n2 (n+1)2 (2n2+2n-1) / 12
6 n (n+1) (2n+1) (3n4+6n3-3n+1) / 42
7n2 (n+1)2 (3n4+6n3-n2-4n+2) / 24
8 n (n+1) (2n+1) (5n6+15n5+5n4-15n3-n2+9n-3) / 90
9n2 (n+1)2 (2n6+6n5+n4-8n3+n2+6n-3) / 20
10 n (n+1) (2n+1) (3n8+12n7+8n6-18n5-10n4+24n3+2n2-15n+5) / 66
11n2 (n+1)2 (2n8+8n7+4n6-16n5-5n4+26n3-3n2-20n+10) / 24
12 n (n+1) (2n+1) (105n10+525n9+525n8-1050n7-1190n6+2310n5
+1420n4-3285n3-287n2+2073n-691) / 2730
13 n2 (n+1)2 (30n10+150n9+125n8-400n7-326n6+1052n5
+367n4-1786n3+202n2+1382n-691) / 420
14 n (n+1) (2n+1) (3n12+18n11+24n10-45n9-81n8+144n7+182n6-345n5
-217n4+498n3+44n2-315n+105) / 90
15 n2 (n+1)2 (3n12+18n11+21n10-60n9-83n8+226n7+203n6-632n5
-226n4+1084n3-122n2-840n+420) / 48

Denominator sequence: 1,2,6,4,30,12,42,24,90,20,66,24,2730,420,90,48...

(2002-11-16)   Multiplicative Functions
An important class of arithmetic functions

An arithmetic function  or  arithmetical function  (in German: zahlentheoretische Funktion)  is a numeric function  (with real or complex values)  of the  positive  integers.  In the context of number theory, an arithmetic function  f  is said to be multiplicative if

f (ab)  =  f (af (b)     whenever the integers a and b are coprime.

If we rule out the function that's identically zero  [as is always done in this context]  this implies that  f(1) = 1  for any multiplicative function  f.

Also, the value of a multiplicative function at zero is always 0  (whenever it's convenient to define that).   [ 1, 2 ]

Excluding, by convention, the zero function from the realm of multiplicative functions ensures that a  unique  multiplicative function is specified by values attributed to the prime-powers, as stated next.  Otherwise, there would be an ambiguity between the zero function and the Dirichlet unit (e) defined below.

To define a multiplicative function, it is sufficient to specify its value when the argument is a  positive  power of a prime ( p).  Here are some examples  (the first seven are easy to compute  without  factoring the argument):

• Dirichlet unit:   e(pn ) = 0   [e(k) = ë1/k û = 0k-1  is zero  unless  k=1]
• Identity function:   N(pn ) = pn   [N(k) = k,  for any k]
• Trivial character:   u(pn ) = 1   [u(k) = 1,  for any positive integer k]
• Character modulo 2:   v(2n ) = 0,  v(pn ) = 1  if p>2   [v(k) = k mod 2]
• Principal character modulo m:   c(pn ) = 0  if p divides m;  1 otherwise.
• Greatest common divisor:   f (pn )  =  gcd(a,pn )   for a given number  a.
• Indicator of the perfect squares:   f (p2n ) = 1   and   f (p2n+1 ) = 0
Note that,  for any positive integer k,  we have:   f (k)  =  so (k) mod 2.

• Number of divisors (so  or  d) :   d(pn ) = n+1.  ["t"   isn't recommended]
• Sum of divisors (s1  or  s) :   s(pn )  =  (pn+1 -1) / (p-1)
• Abundancy:   s-1 (n)  =  s(n) / n   [A perfect number has abundancy 2.]
• Other divisor functions:   sk (pn )  =  (pkn+k -1) / (pk -1)
sk (n)  is the sum of the k-th powers of the divisors of n.
k  can be  negative  (or complex).  Note that:  s-k (n)  =  sk(n) / nk

• Möbius function:   m(p) = -1   and   m(pn ) = 0  for  n>1.
• Euler's totient function:   f(pn )  =  pn-1 (p-1)
f(n)  is the number of integers coprime to n, between 1 and n.
• Pillai's GCD-sum function:  g(pn )  =  (n+1) pn - n pn-1  [K.A. Broughan]
g(n) is the sum of the GCD's with n of the first n integers.  [ g = f*N ]
• Inverse of the above :   g [-1] (pn ) = (p-1)2 or 1-2p if n=1. (A101035)
• Dedekind's psi function:   y(pn )  =  pn-1 (p+1)   (A001615)

• Liouville's function:   l(pn )  =  (-1)n   (A008836)
• Squarefree part:   sf (p2n )  =  1   and   sf (p2n+1 )  =  p   (A007913)
The smallest multiplier which makes a number a perfect square.
• Cubefree part:   cf (pn )  =  p(n mod 3)   (A050985)
• Squarefree kernel  (or "radical") :   rad(pn )  =  p   (A007947)
The  radical  of an integer is the product of its distinct prime factors.
• Multiplicative parity :   g(pn )  =  m(rad(pn ))  =  -1   (A076479).
• Enumeration of Abelian groups :   Abel (pn )  =  p(n)   (A000688)
In this,  p(n)  is simply the number of partitions of n.
• Inverse of the above :   f (pn ) = 0  or (-1) if  n = (3k2 ± k)/2   (A129667)
• Number of squarefree divisors :   f (pn ) = 2   (A034444)
• Number of cubefree divisors :   f (p) = 2   f (pn ) = 3   (A073184)
• Hardy's  Chi function :   c(pn ) = 1, 0 or (-1)  if p is 1, 2 or 3 modulo 4.
Totally multiplicative and period 4:  1, 0, -1, 0, ...  (A056594 or A101455)
• Ramanujan's  Tau function :   t(n)   (A000594)

The ordinary product of two multiplicative functions is itself a multiplicative function  (so is their quotient, assuming a divisor with only nonzero values).  A multiplicative function raised to the power of an integer is also a multiplicative function (so is the nonintegral power of a multiplicative function with positive real values).  Another very interesting type of multiplication, described below, also yields a multiplicative result from two multiplicative operands...

A multiplicative function whose value at the nth power of any prime is a function of  n  only  is said to depend only on the  prime signature  of its argument.  Some examples are:  the Dirichlet unit (e), the trivial character (u), the divisor count (d), the Möbius function (m), Liouville's function (l) and the multiplicative parity (g).  Another example is the aforementioned function  Abel,  which gives the number of  distinct  (i.e., non-isomorphic)  Abelian groups of a given order.

### Multiplicative function  f  summed over all divisors of  n :

The sum of the values of a multiplicative function  f  for all divisor of an integer  n  factorizes into as many factors as  n  has distinct prime divisors.  The factor corresponding to a prime divisor  p  of multiplicity  k  is:

1  +  f ( p )  +  f ( p2 )  +  ...  +  f ( pk )

very important special case  is that of the Möbius function, for which all such factors vanish!  Thus, the values of the Möbius function at all divisors of any positive integer always add up to zero,  unless that integer is just  1  (which has no prime divisors).  That wonderful property is what makes the  Möbius inversion formula  work.  More about that soon...

For any integer  n  > 1
 0   = å m(d) d | n

(2009-05-03)   The Möbius Function  (m)
A table of its values can be computed very fast by  sieving.

The  Moebius function  m  is defined above, as a multiplicative function, in terms of the factorization of its argument  n.  It is equal to zero if  n  is divisible by the square of a prime.  Otherwise,  m(n)  is equal to either  -1  (if  n  has an odd number of prime factors)  or  +1  (when  n  has an even number of prime factors).

A slight modification of the  Sieve of Eratosthenes  can build a table of two-bit entries  (four possible values)  from which  m(n)  can be obtained immediately.  This can be done without performing a single multiplication or division.  The idea is expressed by the following piece of code, which uses  UBASIC  syntax but is really intended to serve as a model for an  assembly language  implementation:

``` 10   ' This puts into M%(n) a two-bit code describing n:
20   '
30   ' 0 = Prime number
40   ' 1 = Product of an odd number of distinct primes.
50   ' 2 = Product of an even number of distinct primes.
60   ' 3 = Multiple of the square of a prime.
70   '
80   Top=3000 ' Running time is O( Top * Log(Log(Top)) )
90   '
100   dim M%(Top) ' Array is initialized with zeroes
110   M%(1)=2 ' 1 is the product of 0 primes (0 is even)
120   '
130   P=2:I=P+P
140   '
150   while I<=Top ' Outer loop
160   '
170   J=2 ' I remains equal to J*P modulo P^2
180   '
190   while I<=Top ' Inner loop
200   if J=P then J=0:M%(I)=3:goto 230
210   X=M%(I):if X=3 then 230
220   if X=1 then M%(I)=2 else M%(I)=1
230   I=I+P:J=J+1
240   wend ' End inner loop
250   '
260   inc P:while M%(P):P=P+1:wend ' Fetch next prime
270   I=P+P
280   wend ' End outer loop
290   '
300   for N=1 to Top ' Check against built-in function
310   if fnMu(N)<>moeb(N) then stop
320   if M%(N)=0 then print N,' DEMO: Show list of primes
330   next N
340   end
350   '
360   fnMu(X)
370   X=M%(X)
380   if X=3 then return(0)
390   if X=2 then return(1)
400   return(-1)```

For the sake of simplicity, this didactic example does not attempt to produce a very compact array.  Ideally, one bit of data per integer will suffice, since it's enough to store 2 bits for each  odd  integer.  Indeed, no even integer  (besides 2)  is prime and  m(2n)  is  either  trivially zero  (if n is even)  or  is found directly from the table for odd numbers, as equal to  -m(n).

The number of additions performed to make a table of size  M  with the above procedure is proportional to the following expression, where k  is a constant and  p  is the largest prime less than or equal to  M/2 :

k.M + M/2 + M/3 + M/5 + M/7 + M/11 + M/13 + ... + M/p

This is  O(M Log Log M)  because the sum of the reciprocal of all primes less than  x  is roughly the  integral  of  1/(x Log x)  which is  Log Log x.  (Incidentally, this argument can be considered the backbone of a proof that a large number N has an average of about  Log Log N  distinct prime factors.)

Note that we cannot abort the procedure at the square root of  M  (as is allowed with the straight Sieve of Eratosthenes)  because we are essentially counting the numbers of prime factors of all indices, not merely determining whether or not there are any such factors.

Although it does grow without bounds, the quantity Log Log x  is equal to  3  for all practical purposes!  (It's exactly that when  x  is around one billion and it changes only by 10% or so when  x  varies by a factor of one thousand.)  The result of the above procedure is thus not worth storing on a computer disk; it can be recomputed faster than it could be loaded back into core memory...

On the number of squarefree integers not exceeding  N

(2002-11-16)   Möbius Inversion Formula  &  Dirichlet Convolution
The weird multiplication in the "Dirichlet ring" of arithmetic functions.  Multiplicative functions form a group under Dirichlet convolution.

### Prototypical Example:  The Sum-Function

If  f  is an arithmetic function, a function  F,  called the sum-function of f,  is defined by letting  F(n)  be the sum of the terms f(d) for all divisors d of n.

If  f  is multiplicative, so is its sum-function  F.

The function   f  may be retrieved from F by using the so-called Möbius inversion formula, which states that  f (n)  is the sum of all terms  F(d) m(n/d)  for all divisors d of n, where m is the Moebius function.

Proof :   å d|n F(d) m(n/d)   =   å å i.j|n f (i) m(j)
In this, the factor of  f (i)  is the sum of all m(j) when j is a divisor of n/i.  That's clearly equal to 1 when i=n.  For all other values of i, the sum over j vanishes, because of a previously made remark

### Generalization:  The Dirichlet Convolution

Lejeune Dirichlet (1805-1859)

Generally, the  Dirichlet product  (or  convolution)  F = f * g  of two arithmetic functions is  defined  by letting  F(n)  be the sum of the terms  f (d) g(n/d)  for all divisors d of n :

 F(n)   =   f * g (n)   = å d | n f (d)  g(n/d)

F is multiplicative whenever f and g are, because any divisor of  n = ab (where a and b are coprime) is the product d = uv of two coprime factors u and v, respectively dividing a and b.  The same is true for  n/d = (a/u)(b/v).  Therefore:

 F(ab)   = å å f(u) g(a/u)  f(v) g(b/v) =   F(a) F(b) u | a v | b

Among  arithmetic functions,  the Dirichlet product (also called Dirichlet convolution) is a commutative and  associative  operation (the value at point  n  of  f*g*h  being the sum of all terms  f(u)g(v)h(w)  where u.v.w = n, for positive integers u,v,w).

Convolution is also distributive over ordinary [pointwise] addition.  Ordinary addition and Dirichlet multiplication thus endow  arithmetic functions  with the structure of a ring, called the  Dirichlet ring.

### Dirichlet Inverse :

For Dirichlet multiplication, the neutral element is the above  Dirichlet unit  (e).  Any arithmetic function  f  for which  f (1)  is nonzero has a  Dirichlet inverse  if we're considering arithmetic functions whose values are in a field.

If   f (1) = 1   (which holds for all  multiplicative  functions)  an arithmetic function  f  whose values are in a ring  (e.g., the ring of integers)  has a Dirichlet inverse with values in the same ring.  Thus, the Dirichlet product endows  multiplicative functions  with the structure of a group.

The Dirichlet inverse of the  trivial character  u  [u(n) = 1]  is the Möbius function m.  This is equivalent to the above  Möbius inversion formula :

If     F  =  u * f     then     f  =  m * F

### Special Examples :

Arguably, the most fundamental examples of Dirichlet convolutions involve the various  powers of the Moebius function  discussed in the next section.

Here are a few  other  examples involving the above standard multiplicative functions, featuring links to Sloane's  Encyclopedia of Integer Sequences :

• A000027:   N   =   u*f   =   m*s
• A000203:   s   =   u*N   =   d*f
• A000010:   f   =   m*N
• A018804:   g   =   f*N

• A055615:   N [-1] (k)   =   k m(k)
• A046692:   s [-1] (pn )   =   (-p-1, p, 0)   for   (n=1, n=2, n>2)
• A023900:   f [-1] (pn )   =   1-p     [Called reciprocity balance.]
• A101035:   g [-1] (p)   =   1-2p     and     g [-1] (pn )   =   (p-1)2 , if n>1.

• A038040:   N*N(k)   =   s*f(k)   =   k d(k)
• A034718:   N*N*N   =   s*g
• A007429:   u*s   =   d*N
• A007430:   d*s
• A007431:   m*f   =   m*m*N
• A007432:   m*m*f   =   m*m*m*N
• A029935:   f*f(pn )   =   (n+1) pn - 2n pn-1 + (n-1) pn-2

(2004-11-27)   Dirichlet Powers of Arithmetic Functions
Dirichlet powers of the Möbius function  m  (and/or its inverse, u = 1).

It's not difficult to show that, for any positive integer q and any arithmetic function  f  with real positive  f(1)  there's a unique root (real positive at point 1) of which  f  is the Dirichlet q-th power.  This defines the Dirichlet 1/q power of  f  and the p/q power of  f  is the p-th power of that thing.  Any such Dirichlet power of a multiplicative function is itself a multiplicative function.

The Dirichlet power  m[k]  of the Möbius function happens to have a very nice  explicit definition  (in terms of its values at the powers of any prime p):

 m[k] (pn )   =   (-1)n C(k,n)

This formula holds even if  k  is  negative  (powers of  u = m[-1] , including  d = u*u ).  More surprisingly, it's also true for  fractional  values of k:

Dirichlet square root of the Möbius function :   m [ ½ ] (p)  =  (-1)n C(½,n)
m = 123456789 101112
m[½] (m)  1 -1/2-1/2-1/8-1/21/4 -1/2-1/16-1/81/4-1/21/16

Whole  powers of the Möbius function  m  and/or its inverse  u  include:

• A063524:   e   =   e*e   =   u*m   =   d*(m*m)   =   m[0]
• A008683:   m(pn )   =   resp. (-1, 0)   for   (n=1, n>1)
• A007427:   m*m(pn )   =   resp. (-2, 1, 0)   for   (n=1, n=2, n>2)
• A007428:   m*m*m(pn )   =   (-1)n C(3,n)
• A000012:   u   =   m*d   =   m[-1]
• A000005:   d   =   u*u   =   m[-2]
• A007425:   d*u   =   u*u*u   =   m[-3]
• A007426:   d*d(pn )   =   C(n+3,3)   =   (-1)n C(-4,n)   [A000292]

(2009-11-14)   Dirichlet Powers of a Multiplicative Function  f
Their values on  { pn | n = 1,2,3... }  depend only on values of  f  there.

A multiplicative function  f  can be specified by giving, for every prime p, the  generating function  of the values of f  at the powers of  p.  Conversely, any family of formal generating functions  (i.e., power series)  indexed by the primes and such that  yp(0) = 1  uniquely determines a multiplicative function, provided only that

yp (z)   =   å n  f (pn )  zn

The following beautiful formula determines the Dirichlet power of  f  for any exponent  k  (the  Dirichlet inverse  of  f  is obtained for  k = -1 ).

 yp (z) k   =   å n  f [k] (pn )  zn

A similar relation  defines  the Dirichlet product of two multiplicative functions:

( å n  f (pn )  zn ) ( å n  g (pn )  zn )     =     å n   f *g (pn )  zn

Essentially, a  multiplicative function  is thus usefully described as an object with infinitely many components  (one for each prime p)  each consisting of a sequence starting with  1  (one).  The  Dirichlet convolution  (or Dirichlet product)  of two such things is the object whose components are ordinary  Cauchy products  of the corresponding pairs of component sequences.  That's all there is to it.

(2002-11-16)   Completely  Multiplicative Functions
The simplest type of multiplicative functions.

A function  f  is called completely multiplicative (or totally multiplicative) when  f(ab) = f(a) f(b always holds  (whether a and b are coprime or not)  in which case its Dirichlet inverse  g  is easily defined:   g(n) = m(n) f(n), since:

 g*f (n)   = å m(d) f(d) f(n/d)   =   f(n) å m(d)   =   f(n) e(n)   =   e(n) d | n d | n

The last equality holds for n=1 because  f(1)=1, and for n>1 because e(n)=0.

A completely multiplicative function  f  and its dirichlet inverse  g  are entirely determined by whatever values  f(p)  are chosen for prime numbers p, since:

f (pn )  =  f (p) n     whereas     g(p) = - f (p)    &    g(pn ) = 0,   if n>1

That's just a special case of the above formula, with   yp (z) -1  =  1- f (p) z

A multiplicative function which is zero for squares of primes, and higher powers of prime numbers, is thus the Dirichlet inverse of a totally multiplicative function.

This applies, in particular, to the  Dirichlet characters  (presented next)  as they are indeed  totally multiplicative.

(2002-11-16)   Dirichlet Characters
An important example of  totally multiplicative functions.

A Dirichlet character modulo k  (also called  character to the modulus k )  is a complex-valued  completely multiplicative  function of period k, which vanishes whenever its argument isn't coprime with k.

The  conductor  of a given Dirichlet character is its  smallest  period.  The characters to the modulus k with conductors equal to k are called  primitive  (those whose conductors are proper divisors of  k  are called  imprimitive ).

There are exactly  f(k)  possible Dirichlet characters to the modulus k  (where f is Euler's totient function).  They are tabulated below for some small values of  k.

Except for k=3, k=4 and k=6 (which could have been tabulated together) we've spared the expense of separate tables for isomorphic structures.  Instead, we indicate at the bottom of the relevant tables how to relabel the columns for additional values of k  (a wildcard label '*' is to be used for unlisted values of n, which correspond to zero columns because they're not coprime with k).

For example, such an isomorphism exists among all the values of k (7, 9, 14 and 18) for which f(k)=6, as there's only one Abelian group of order 6.  On the other hand, the two distinct 4-line structures correspond to the two Abelian groups of order 4:  The cyclic group (k=5, k=10) and the Klein group (k=8, k=12).

 n 0 1

 n c1 (n) 1 0 1 0
 n c1 (n) c2 (n) c3 (n) c4 (n) 1 2 3 4 0 1 1 1 1 0 1 i -i -1 0 1 -i i -1 0 1 -1 -1 1 0 k = 10 1 3 7 9 *

 n c1 (n) c2 (n) 1 2 0 1 1 0 1 -1 0

 n c1 (n) c3 (n) 1 2 3 0 1 0 1 0 1 0 -1 0
 n c1 (n) c5 (n) 1 2 3 4 5 0 1 0 0 0 1 0 1 0 0 0 -1 0
 n c1 (n) c2 (n) c3 (n) c4 (n) c5 (n) c6 (n) 1 2 3 4 5 6 0 1 1 1 1 1 1 0 1 w2 -w -w w2 1 0 1 -w -w2 w2 w -1 0 1 -w w2 w2 -w 1 0 1 w2 w -w -w2 -1 0 1 1 -1 1 -1 -1 0 k=9 1 4 2 7 5 8 * k=14 1 9 3 11 5 13 * k=18 1 13 11 7 5 17 *

 n c1 (n) c3 (n) c5 (n) c7 (n) 1 2 3 4 5 6 7 0 1 0 1 0 1 0 1 0 1 0 -1 0 1 0 -1 0 1 0 1 0 -1 0 -1 0 1 0 -1 0 -1 0 1 0 k=12 1 * 5 * 7 * 11 *
w  =  exp ( ip/3 )  =  (1+iÖ3) / 2
[ w3 = -1 ]

 n c1 (n) c2 (n) c3 (n) c4 (n) c5 (n) c6 (n) c7 (n) c8 (n) c9 (n) c10 (n) 1 2 3 4 5 6 7 8 9 10 0 1 1 1 1 1 1 1 1 1 1 0 1 x -x3 x2 x4 -x4 -x2 x3 -x -1 0 1 -x3 x4 -x x2 x2 -x x4 -x3 1 0 1 x2 -x x4 -x3 -x3 x4 -x x2 1 0 1 x4 x2 -x3 -x -x -x3 x2 x4 1 0 1 -x4 x2 -x3 -x x x3 -x2 x4 -1 0 1 -x2 -x x4 -x3 x3 -x4 x x2 -1 0 1 x3 x4 -x x2 -x2 x -x4 -x3 -1 0 1 -x -x3 x2 x4 x4 x2 -x3 -x 1 0 1 -1 1 1 1 -1 -1 -1 1 -1 0 k=22 1 7 9 5 3 19 17 13 15 21 *
 n c1 (n) c2 (n) c3 (n) c4 (n) c5 (n) c6 (n) c7 (n) c8 (n) c9 (n) c10 (n) c11 (n) c12 (n) 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 y y4 y2 -y3 y5 -y5 y3 -y2 -y4 -y -1 0 1 y4 y4 -y2 1 -y2 -y2 1 -y2 y4 y4 1 0 1 y2 -y2 y4 -1 -y4 y4 -1 y4 -y2 y2 1 0 1 -y3 1 -1 -y3 -y3 y3 y3 1 -1 y3 -1 0 1 y5 -y2 -y4 -y3 y -y y3 y4 y2 -y5 -1 0 1 -y5 -y2 -y4 y3 -y y -y3 y4 y2 y5 -1 0 1 y3 1 -1 y3 y3 -y3 -y3 1 -1 -y3 -1 0 1 -y2 -y2 y4 1 y4 y4 1 y4 -y2 -y2 1 0 1 -y4 y4 -y2 -1 y2 y2 -1 -y2 y4 -y4 1 0 1 -y y4 y2 y3 -y5 y5 -y3 -y2 -y4 y -1 0 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 k=26 1 7 9 23 21 11 15 5 3 17 19 25 * We didn't simplify y2  and y3  to w and i  (to allow y to be any primitive 12-th root of unity).
n c1 (n) c2 (n) c4 (n) c7 (n) c8 (n) c11 (n) c13 (n) c14 (n) 1 2 4 7 8 11 13 14 1 1 1 1 1 1 1 1 1 i -1 -i -i -1 i 1 1 -1 1 -1 -1 1 -1 1 1 -i -1 -i i 1 i -1 1 -i -1 i i -1 -i 1 1 -1 1 1 -1 -1 1 -1 1 i -1 i -i 1 -i -1 1 1 1 -1 1 -1 -1 -1 k=16 1 3 9 5 11 7 13 15 k=20 1 7 9 17 3 11 13 19 k=30 1 17 19 7 3 11 13 29

 1 5 7 11 13 17 19 23 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 0 1 2 3 4 5 6 7
Multiplicative residues modulo 24 are like additive 3-bit vectors.

Collectively, the  f(k)  characters modulo k form a group  with respect to pointwise multiplication  (isomorphic  to the multiplicative group of the residues coprime to k)  whose neutral element is the so-called  principal  Dirichlet character modulo k (whose value is 1 for an argument coprime to k and 0 otherwise).  It is denoted by the symbol  c1  in the above tables.

This should not be confused with the  trivial character  (denoted above by the symbol  u )  which is the unique character to the modulus 1  and whose value is simply 1 for all positive integers  [and 0 at point 0].

We have indexed the characters in those tables with the multiplicative residues modulo k  themselves, in accordance with the aforementioned isomorphism (for the smallest relevant k).  This convention makes the above tables symmetrical:

cm (n)   =   cn (m)

Except in the trivial cases  (i.e., k = 1, 2, 3, 4 or 6)  there are  several  indexing scheme with this property  (because several automorphisms exist).  Thus, the above does not assign unambiguous names to the various Dirichlet characters.

Some (real) Dirichlet characters are obtained by generalizing the Legendre symbol  (of quadratic reciprocity fame).  Generalized versions of the Legendre symbol often go by other names  (Jacobi symbol or Kronecker symbol)  which we don't advocate, because such nomenclature is not technically needed...

c(n)   =   ( n | k )

The above tables have been arranged to make this particular character appears in the last row (green shading).  Recall that the Kroneker generalization of the Legendre symbol obeys the following ad hoc conditions:

   a mod 8  ( a | 2 ) 0 1 2 3 4 5 6 7 0 1 0 -1 0 -1 0 1

If  k  is  1, 2, 4, the power of an odd prime, or  twice  the power of an odd prime  (A033948)  then the corresponding group is cyclic  (i.e., it has a primitive root).  In that case, we may consider a given primitive root  r  of the multiplicative group formed by the invertible elements modulo k,  often denoted (/k)*,  and state that every character  c  modulo k is obtained by the following defining relation for  some  f(k)-th  root of unity  z  (not necessarily a primitive one).

" n     c (rn )   =   z n

Some of the above tables were obtained this way, simply by sorting columns in ascending order of the arguments  (r n ).  Here's another way to present things:

 c ( n ) 1 z z2 z3 z4 z5 z6 z7 z8 z9 z10 z11 z12 z13 z14 z15 0 k=17 1 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 0 k=34 1 3 9 27 13 5 15 11 33 31 25 7 21 29 19 23 *

 c ( n ) 1 z z2 z3 z4 z5 z6 z7 z8 z9 z10 z11 z12 z13 z14 z15 z16 z17 k=19 1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 k=27 1 5 25 17 4 20 19 14 16 26 22 2 10 23 7 8 13 11 k=38 1 3 9 27 5 15 7 21 25 37 35 29 11 33 23 31 17 13 k=54 1 5 25 17 31 47 19 41 43 53 49 29 37 23 7 35 13 11

The same compact tabulation may be used for non-cyclic groups  (A033949).  We may illustrate that with the smallest modulus not yet encountered  (k=21):

 c ( n ) 1 y y2 y3 y4 y5 x xy xy2 xy3 xy4 xy5 0 k=21 1 5 4 20 16 17 13 2 10 8 19 11 * k=42 1 5 25 41 37 17 13 23 31 29 19 11 *

The  Dirichlet characters modulo k  are just the homomorphisms from the multiplicative group  (/k)*  into the group of the  f(k)-th  roots of unity.

(2007-04-17)   Euler Products and Generalized Zeta Functions
Consider the series   F(s)  =  Sn  f (n) n-s   for some value of s.

If  f  is a multiplicative function, this can be expressed as an  Euler product ,  namely an infinite product whose factors are functions of all the consecutive primes: p = 2, 3, 5, 7, 11, ...   (HINT:  Every coefficient  f (n)  appears in the expansion of this product, tied to the unique factorization of  n  into primes.)

Pp  ( 1  +  f (p) p-s  +  f (p2 ) p-2s  +  f (p3 ) p-3s  +  f (p4 ) p-4s  +  ... )

This  formal  equality  (discarding issues of numerical convergence)  holds  if and only if  the function  f  is  multiplicative, in the sense specified above.

When  f  is totally multiplicative, each Euler factor becomes a geometric series, which we may sum up to obtain the simple relation:

F(s)   =   Sn  f (n) n-s   =   Pp  ( 1  -  f (p) p-s ) -1

When  f (n) = 1  for any n  (with the above notations, f  is the trivial character  u )  that relation expresses Riemann's  zeta function  F(s) = z(s).

z(s)   =   Sn  n-s   =   Pp  ( 1  -  p-s ) -1

If  f  is a Dirichlet character c, the above is called a  Dirichlet L-function :

L(c,s)   =   Sn  c (n) n-s   =   Pp  ( 1  -  c (p) p-s ) -1

Such functions aren't limited to values of s which make the series converge; they are extended by  analytic continuation, as is the  zeta function  itself.  We may single out the case of the two characters modulo 4, which yields:

L(c1,s)   =   (1-2-s ) z(s)       and       L(c2,s)   =   b(s)

Establishing the first equation is a simple exercise left to the reader.  The second equation defines what's known as Dirichlet's Beta Function, which extends, by analytic continuation, over the entire complex plane without any singularities.

### Introducing the Hurwitz Zeta Function

Dirichlet L-functions can be expressed in terms of yet another generalization of Riemann's zeta function, known as the  Hurwitz zeta function:

z(s,q)   =   Sn  (n+q)-s

The parameter  q  is usually assumed to be a real between 0 and 1, although the function is well defined for other values of  q.

The L-function for any Dirichlet character c to the modulus k  is simply a linear combination of Hurwitz zeta functions (for rational values of q):

L(s,c)   =   k-s
 k å n=1
c(n) z(s,n/k)

Conversely, the value (function of s) of the  Hurwitz zeta function  for a proper fraction  q = n/k  (expressed in lowest terms) is also given as a finite sum over all the Dirichlet characters  c  to the modulus k, namely:

z(s,n/k)   =   Sc  c(n) L(s,c)

Dirichlet's theorem           Wikipedia :     Euler product   |   L-functions   |   Hurwitz zeta function