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 20040614,
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 nontrivial 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.
What you're describing are, in fact, the irreducible
elements of a ring;
those which cannot be expressed as a nontrivial 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.
(20020616)
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...
Anonymous query, via Google (20041105)
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
(20020614)
Gaussian Integers, Gaussian Primes, etc.
How does the concept of primality generalize beyond ordinary integers?
The socalled Gaussian integers are
complex numbers of the form
a+ib, where a and b are integers.
Gauss showed that each Gaussian integer has a unique factorization
as a product of a socalled "unit" (one of the 4 invertible
elements +1, 1, +i, i ) and irreducible elements in
an abitrarily chosen "quarter" of the complex plane,
equivalent to positive primes among ordinary integers
(in this context, a Gaussian integer x+iy is said to be
"positive" when
x < y < x+1 ).
Note that 1+i is the only "positive" Gaussian prime whose conjugate
is not a "positive" Gaussian prime as well
(since 1i = (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) (2i)
Note that the above factorization of 2
(involving the "unit" i) is indeed the proper "unique" one, since the
more obvious factorization (1+i)(1i)
uses a Gaussian integer which is not "positive" in the above sense...
AlisonWonder
(20020623)
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 2^{3}´3.
86 is 2´43. 125 is 5^{3}.
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:
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:
Note:
The above numbers (a and b) are not random ones.
They are both products of two very special 19digit prime numbers...
HINT: Their GCD is 1111111111111111111 and the other factors are of a similar nature
(in nondecimal bases of numeration).
vorobya
(Alexey Vorobyov.
20021018)
Aurifeuillian Factorizations
Prove that n^{4} + 4 is composite (i.e., not prime) for all n
> 1
Well,
n^{4} + 4 = (n^{2}  2n + 2) (n^{2} + 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 (18221882,
X1841)
whose factorization methods were applied by
Henri Le Lasseur de Ranzay
(an enthusiastic amateur who owned
the Château du BoisHue in SaintJoseph du Portricq,
near Nantes). Le Lasseur routinely shared his factorizations with
Edouard Lucas and
Eugène Catalan.
The selfstyled "vicomte" Alfred de Caston claimed to be a native of America.
He once lived in Turkey
where he became editorinchief of the
Revue de Constantinople in 18751876.
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 20120212)
appeared in the French magazine L'Escamoteur
(45, marchapril 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 :
In 1871, Aurifeuille himself used the first of those equations
(with n = 14)
to obtain immediately the following celebrated factorization:
2^{58} + 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
(b. 1798, fl. 1882)
after casting out the factor 5.
Summarizing his factorizations in 1869, Landry wrote:
None of the numerous factorizations of the numbers
2^{n} ± 1
gave as much trouble and labor as that of
2^{58} + 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
2^{58} + 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):
(20060205)
Euclid's Algorithm establishes Bézout's Theorem
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 socalled 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 Theorem).
Subtractive Version of Euclid's Algorithm :
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).
(20060205)
Bézout's Theorem (Bézout's Identity):
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 fundamental (very useful) result is named after the French mathematician
Etienne
Bézout (17301783) although it was already wellknown
before his time.
In particular, it's featured in the work of
Claude
Gaspar Bachet de Méziriac (15811638) who gave his name to
Bachet squares (1624).
One 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):
Note that u is defined modulo q and v is defined modulo p, because:
u p + v q = (u+kq) p + (vkp) q
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 socalled
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).
That's an unpalatable exception (a noninteger value)
for just one trivial case.
(It's more natural to retain
bezout (x, ±x) = 0
rather than insist on the above.)
Forsaking that ad hoc exception,
here's how to define bezout
on a TI92, TI89 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
(xt)/y®q
y®x : t®y
uq*v®t : v®u : t®v
EndWhile
u : EndFunc
Note that bezout is odd for one argument
and even for the other:
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 HewlettPackard calculators (HP49g+, HP50g)
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 3instruction program yields what we need modulo y.
Incidentally, 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.
(As angle measurements are totally irrelevant to this function,
this is definitely to be regarded as a bug, although it merely causes inconvenience but no errors.)
(20070507)
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 commensurableiff 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
A 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
(20020402)
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 Î :
x_{n} = 1 + 2 n
y_{n} = 4  3 n
Any such equation whose unknown variables are required to be integers is called
a Diophantine equation.
Here's how to proceed to solve for x and y any
linear Diophantine equation
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 theorem).
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' (xuc') + b' (yvc') = 0
Therefore, b' divides the product a' (xuc').
Since b' and a' are coprime, b' must divide
(xuc').
In other words, there exists an integer k such that
x = u c' + k b'
and we see that the equation does hold if
y = v c'  k a'.
For the numerical example a = 1024,
b = 15625, c = 8404, we obtain:
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 have smaller constants, we may want to introduce n = 2569  k
x = 3121 + 15625 n
y = 204 + 1024 n
Indeed: 1024 ( 3121 + 15625 n ) 
15625 ( 204 + 1024 n ) = 8404
(20060203)
Pythagorean Triples (Pythagorean Triplets)
Solutions, in coprime positive integers, of the equation
x^{2} + y^{2} = z^{2}
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).
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) (zx)
The positive integers ½(z+x) and ½(zx) are coprime
(or else the sum and the difference, z and x, wouldn't be coprime).^{ }
As their product is a square (a^{2})
both of them are.
So, there are two integers u and v such that:
z+x = 2u^{2} and zx = 2v^{2},
which implies y^{2} = (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
1
3
5
15
7
21
35
9
45
11
33
63
55
13
77
y
0
4
12
8
24
20
12
40
28
60
56
16
48
84
36
z
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.
The numbers that are expressible in many ways as sums of two squares
(A016032)
enjoy an unfair advantage in the above recordbreaking game.
(Joe of Ann Arbor, MI.
20001024)
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 = A^{a}B^{b}C^{c}...
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.
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:
N is the product of 3 distinct primes.
N is the product of a prime by the cube of another prime.
N is the seventh power of a prime.
There are a lot more solutions this time:
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.
The second class starts with 2^{3}´3=24,
2^{3}´5=40, 2´3^{3}=54, 2^{3}´7=56,
2^{3}´11=88, 2^{3}´13=104, 3^{3}´5=135,
2^{3}´17=136, etc.
The third class is the sequence of seventh powers of primes:
128, 2187, 78125, 823543, etc.
(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.)
(20100125)
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 = A^{a}B^{b}C^{c}... 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.
Anonymous query, via Google
(20101009)
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 = p^{k }Q
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.
(J.E. of Lubbock, TX.
20001025)
Perfect Numbers, Mersenne Primes
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 p^{m} (p is prime and m is its multiplicity in the factorization);
s(n)/n is the product of the
factors (p^{m+1}1)/(p^{m+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 60120 ; 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 the even
perfect numbers are of the form given by Euclid, namely:
2^{n1}(2^{n}1), provided
(2^{n}1) is prime.
Such a prime number (i.e., one unit less than a power of 2)
is known as a Mersenne prime.
Marin Mersenne (15881648)
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.
Mersenne's first two mistakes were to omit exponent 61 and to include exponent 67.
Exponent 67 was shown to yield a composite Mersenne number (by Edouard
Lucas, around 1875) well before Frank Nelson Cole (18611926) could
heroically find its factors, in 1903.
As of July 2014,
only 48 Mersenne primes are known, corresponding to the following values of the
exponent (n):
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 (18421891) 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 LucasLehmer 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 (19111995), 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 (20020526 email)
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.
Are there any odd perfect numbers?
Nobody knows...
Finding an odd perfect number, or showing that none exist,
is one of the oldestunsolved 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:
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 10^{8}.
Jenkins had established a lower bounded of 10^{7} in
2003.
The same method was used by Goto and Ohno in 2006 to improve the lower bound to
10^{8}.
At least one prime power greater than 10^{20}.
[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. 267277) 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.
A sum of the exponents in the prime factorization which 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
2^{4k}
[Nielsen 2003].
MathWorld

OddPerfect.org by William Lipp
(still under construction as of 20071201)
Seminar
by Oliver Knill (Dec. 2007)
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.
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 3perfect numbers. Indeed,
if W was a [ huge ]
odd perfect number,
then the abundancy of 2W would be
a(2) ´ a(W) = 3.
In 1925, Paul Poulet (18871946)
reported the first two 8perfect numbers; they're both multiples of 2^{62} with
42 and 43 distinct prime factors, respectively.
As of 2010, the only known number n = 2.5185... 10^{1906} for which
s(n)/n = 11 is a
monster of 246 prime factors, found by
George F. Woltman
on March 13, 2001:
Thanks to Michel Marcus
for contributing to the extensions of the above tables
[ 11/2 
13/2 ].
Note that, if the prime 2q1
isn't a factor of n, then:
(2q1)
s_{1 }( n (2q1) ) =
2q s_{1 }(n)
Thus, if the abundancy of n (2q1) happens to be q,
then the abundancy of n is equal to q1/2.
This way, a few hemiperfect numbers are obtained from some multiperfect numbers.
For example, with 2q1 = 5
the above applies to the three 3perfect 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 (20090915)
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:
The above replacement of the partial factorization
7^{1 }19^{0} by
7^{2 }19^{1} 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 20090928:
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:
Michel Marcus first found
(the hard way) a
97digit integer of abundancy 15/2
on July 4, 2009. He then found
many more,
including the following 89digit number of abundancy 15/2,
discovered on August 15, 2009 :
As of 2010,
the smallest known 9perfect number is a 287digit 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).
(G. S. of Farley, IA.
20001115)
How can a power ,
like 12^{17}, 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´10^{18}.
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 routinely use the above approach to compute a^{n}modulo m
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 consider only the remainder of the division by m,
which remains less than m.
(Steve of Somerville, MA.
20001116) _{ }
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 are 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 (18871920). He collaborated with
J.H.
Hardy (18771947) 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 9799 of Littlewood's Miscellany by
John
E. Littlewood (18851977). In 1937,
Hans Rademacher (18921969) gave a formula for p(n) as a convergent series
("On the partition function p(n)" Proc. London Math. Soc. 43 (1937) 241254).
The number of partitions p(n) is the coefficient of x^{n} in the expansion of
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 (17071783) as the reciprocal of the products of
all factors (1x^{n}) 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.
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+x^{u}+x^{2u}+x^{3u}+ ...).
(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(kj)
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*kk)\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 partitionbased 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}
(20110121) Ken Ono's great
epilog on the partition function.
Ken
Ono, 2011 Emory University Photo 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).
DrGerard (Gérard Michon from Los Angeles, CA.
20001118)
Let M be the sequence ^{ } M_{0}= 0, M_{1}= 1, and
M_{n+2} = M_{n+1}  2 M_{n} 0, 1, 1, 1, 3, 1,
5, 7, 3, 17, 11, 23, 45, 1, 91, 89, 93, 271, ...
The Binet formula
for M_{n} is :
M_{n} = (2/Ö7) 2^{n/2}
sin (n atan Ö7 ) Considering this sequence modulo 8, it's clear that
M_{n} cannot be equal to 1 if n > 2.
Prove that M_{n} 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 secondorder
linear recurrence relation:
Lemma(s) :
If U_{0} = 0, U_{1} = 1, and
U_{n+2} = A U_{n+1} + B U_{n} then, for
any sequence V such that V_{n+2} = A V_{n+1} + B V_{n}
we have:
V_{n} = V_{0} U_{n+1} +
(V_{1}  A V_{0 }) U_{n}
(This is easily established by induction on n.)
In particular, with V_{n} = U_{n+k+1} :
U_{n+k+1} = U_{n+1} U_{k+1}
+ B U_{n} U_{k}
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):
U_{p} Ù U_{q} =
 U_{pÙ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
U_{q+1} Ù U_{q} = 1.
We use the above lemma with n+k+1 = p
and k = q :
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 20001118 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
(20020608)
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, 20020610 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 have printed [this proof] for posterity [but] what's
the significance of it all?
[Donaldekliros,
20020713]
In any integer sequence which
(like M) starts with 0 and 1 and obeys a secondorder 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 sequenceA000225.
Similarly, Fibonacci primes occur only at prime indices within the
Fibonacci sequenceA000045,
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 M_{n} is prime, namely:
(20090629)
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 :
U_{0} = 0, U_{1} = 1,
U_{n+2} = A U_{n+1} + B U_{n}
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).
(20080506) A sequence of bits
with strange statistics
On the number of perfect squares between two consecutive cubes.
Let's count the squares
between n^{3} (included)
and (n+1)^{3} (excluded):
n^{3}
Perfect Squares
Count
0
0
1
1
1, 4
2
8
9, 16, 25
3
27
36, 49
2
64
64, 81, 100, 121
4
125
144, 169, 196
3
216
225, 256, 289. 324
4
343
361, 400, 441, 484
4
512
529, 576, 625, 676
4
729
729, 784, 841, 900, 961
5
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 = 3n^{2}+3n+1
numbers between m = n^{3}
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:
A closed formula for this bit sequence
is easy to obtain:
b_{n} = ^{ }
(_{ }n^{3} + 3n^{2} + 3n_{ })^{ 1/2}

n_{ }^{3/2}
+ 1 
3
n_{ }^{1/2}
2
This sequence of pseudorandom 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 longperiod 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 shortrange 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" pseudorandom sequence
which unexpectedly fails to obey longrange 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 longrange 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...
(20071202) Binet's Formulas
(Euler c. 1730, Binet 1843)
The nth term in a sequence obeying a secondorder recurrence.
For two given constants A and B,
consider the sequences V which obey
V_{n+2} = A V_{n+1} + B V_{n}
Those form a twodimensional vector space, where
each element is entirely determined by its "coordinates"
(V_{0 }, V_{1 }).
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 nth term is
U_{n+1}
Now, consider the following sequence W :
W_{n} = 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 nth term of any sequence
V is of the form:
V_{n} =
x a^{n}
+
y b^{n}
where
(za)(zb)
=
z^{ 2}  A z  B
In particular, for the sequence U
(which starts with U_{0} = 0 and U_{1} = 1) :
U_{n} = ^{ }
a^{n}_{ } b^{n}
a  b
In the special case when a = b
the above breaks down. Instead, we have:
U_{n} =
n a^{ n1}
Such explicit expressions are called Binet formulas,
in honor of the influential French mathematician
Jacques Binet
(17861856; 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) :
F_{n} =
[ f^{n}

(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 formulas predate Binet by more than a century
(they were known to Euler).
D'Alembert
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 secondorder 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) :
V_{n} = V_{0} U_{n+1} +
(V_{1}  A V_{0 }) U_{n}
Usage Note :
Any explicit formula for the nth 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 thirdorder Binet formula).
(20071129)
Cassini's Identity (1680)
If U_{0} = 0, U_{1} = 1, and
U_{n+2} = A U_{n+1} + B U_{n} then:
V_{n} =
U_{n}^{2}

U_{n+1} U_{n1}
= (B)^{n1} 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
JeanDominique Cassini (16251712)
and it has been rediscovered many times since, most notably by
Robert
Simson (16871768; pedal line) in 1753.
Proof :
Using V_{1} = 1, the general case is established
by induction on n :
V_{n+1} =
(A U_{n} + B U_{n1 }) U_{n+1}

(A U_{n+1} + B U_{n }) U_{n}
= (B) V_{n}
(20071129)
d'Ocagne's Identity
A generalization of Cassini's Identity
due to Maurice d'Ocagne.
U_{n} U_{m+1} 
U_{n+1} U_{m} =
(B)^{m } U_{nm}
[ where n ≥ m ]
Proof :
For a given value of m, let's consider the following function of i :
W_{i} =
U_{m+i} U_{m+1} 
U_{m+i+1} U_{m}
As W_{0} = 0, the
above lemma shows that
W_{i} = W_{1 }U_{i} where the value
W_{1} = (B)^{m} is obtained
immediately from Cassini's Identity.
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
V_{n} = (ab) U_{n}
V_{n} = a^{n}
 (B/a)^{n}
Well, let's just evaluate
V_{n}^{2} 
V_{n+m} V_{nm} :
Kirk Guidry (20020330; email)
Faulhaber's Formula
[...]
For a given p, how do you derive a formula for the sum of the pth 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.
[...]
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 p^{th} 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:
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
0
n+1^{ }
1
n (n+1) / 2^{ }
2
n (n+1) (2n+1) / 6^{ }
3
n^{2} (n+1)^{2} / 4
4
n (n+1) (2n+1) (3n^{2}+3n1) / 30
5
n^{2} (n+1)^{2} (2n^{2}+2n1) / 12
6
n (n+1) (2n+1) (3n^{4}+6n^{3}3n+1) / 42
7
n^{2} (n+1)^{2}
(3n^{4}+6n^{3}n^{2}4n+2) / 24
8
n (n+1) (2n+1)
(5n^{6}+15n^{5}+5n^{4}15n^{3}n^{2}+9n3) / 90
(20021116) Multiplicative Functions
An important class of arithmetic functions:
An arithmetic function (more rarely, arithmetical function)
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 (a) f (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).
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^{n }). Here are some examples_{ }
(the first seven are easy to compute withoutfactoring the argument):
Dirichlet unit:
e(p^{n }) = 0 [e(k) =
ë^{1}/_{k
}û
= 0^{k1} is zero unless k=1]
Identity function: _{ }
N(p^{n }) = p^{n} [N(k) = k, for any k]
Trivial character:
u(p^{n }) = 1 [u(k) = 1,_{ } for any positive integer k]
Character modulo 2:
v(2^{n }) = 0,
v(p^{n }) = 1 if p>2 _{ }
[v(k) = k mod 2]
Principal character modulo m:
c(p^{n }) = 0
if p divides m;_{ } 1 otherwise.
Greatest common divisor: _{ }f (p^{n }) = gcd(a,p^{n })
for a given number a.
Indicator of the perfect squares: f (p^{2n }) = 1 and f (p^{2n+1 }) = 0 Note that, for any positive integer k, we have:
f (k) = s_{o }(k) mod 2.
Number of divisors (s_{o } or d)
: d(p^{n }) = n+1.
Sum of divisors (s_{1} or
s) :
s(p^{n }) =
(p^{n+1 }1) / (p1)
Abundancy:
s_{1 }(n) =
s(n) / n ^{ }
[A perfect number has abundancy 2.]
Other divisor functions:
s_{k }(p^{n }) =
(p^{kn+k }1) /
(p^{k }1)
s_{k }(n) is the sum of the kth powers of the
divisors of n.
k can be negative (or
complex). Note that:
s_{k }(n) =
s_{k}(n) / n^{k}
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 n^{th} 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 which gives the number of
distinct (i.e., nonisomorphic) 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 ( p^{2 })
+ ... + f ( p^{k })
A 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
(20090503) 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
(if n has an even number of prime factors).
A slight modification of the
Sieve
of Eratosthenes can build
a table of twobit 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 twobit 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 builtin 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 :
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 than
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...
(20021116) 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 SumFunction
If f is an arithmetic function, a function F,
called the sumfunction of f, is defined by letting F(n)
be the sum of the terms f(d) for all divisors d of n.
The function f may be retrieved from F by using the socalled
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 :
å_{ dn} F(d) m(n/d)
=
å å_{ i.jn}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
(18051859)
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
aboveDirichlet 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 :
(20041127) 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 qth power.
This defines the Dirichlet 1/q power of f
and the p/q power of f is the pth 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] }(p^{n })
= (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^{n }) =
(1)^{n }C(½,n)
m =
1
2
3
4
5
6
7
8
9
10
11
12
m^{[½] }(m)
1
1/2
1/2
1/8
1/2
1/4
1/2
1/16
1/8
1/4
1/2
1/16
Whole powers of the Möbius function
m and/or its inverse u include:
(20091114)
Dirichlet Powers of a Multiplicative Function f
Their values on { p^{n}  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
y_{p}(0) = 1
uniquely determines a multiplicative function, provided only that
y_{p }(z) =
å_{ n}f (p^{n }) z^{n}
The following beautiful formula determines the
Dirichlet power of f for any exponent k
(the Dirichlet inverse of f
is obtained for k = 1 ).
y_{p }(z)^{ k} =
å_{ n}f^{[k] }(p^{n }) z^{n}
A similar relation defines the Dirichlet product of two
multiplicative functions:
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.
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 (p^{n }) =
f (p)^{ n}
whereas
g(p) =  f (p)
&
g(p^{n }) = 0, if n>1
That's just a special case of the above formula, with
y_{p }(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.
A Dirichlet character modulo k
(also called character to the modulus k )
is a complexvalued
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 4line 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).
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 socalled principal Dirichlet character modulo k
(whose value is 1 for an argument coprime to k and 0 otherwise).
It is denoted by the symbol c_{1}
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:
c_{m }(n)
=
c_{n }(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  1 ) = sign(a)
a mod 8
0
1
2
3
4
5
6
7
( a  2 )
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_{ }(r^{n })
= 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:
f(k) = 16
z^{16} = 1
c^{ }( n )
1
z
z^{2}
z^{3}
z^{4}
z^{5}
z^{6}
z^{7}
z^{8}
z^{9}
z^{10}
z^{11}
z^{12}
z^{13}
z^{14}
z^{15}
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
*
f(k) = 18
z^{18} = 1
c^{ }( n )
1
z
z^{2}
z^{3}
z^{4}
z^{5}
z^{6}
z^{7}
z^{8}
z^{9}
z^{10}
z^{11}
z^{12}
z^{13}
z^{14}
z^{15}
z^{16}
z^{17}
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 noncyclic groups
(A033949).
We may illustrate that with the smallest modulus not yet encountered (k=21):
f(k) = 12
x^{2} = 1
y^{6} = 1
c^{ }( n )
1
y
y^{2}
y^{3}
y^{4}
y^{5}
x
xy
xy^{2}
xy^{3}
xy^{4}
xy^{5}
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 homeomorphisms from the multiplicative group
(/k)* into
the group of the f(k)th roots of unity.
(20070417) Euler Products and Generalized Zeta Functions
Consider the series F(z) =
S_{n}f (n) n^{z}
for some value of z.
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.)
P_{p}
( 1 + f (p) p^{z}
+ f (p^{2 }) p^{2z}
+ f (p^{3 }) p^{3z}
+ f (p^{4 }) p^{4z}
+ ... )
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:
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(z) = z(z).
z(z) =
S_{n} n^{z}
=
P_{p}
( 1  p^{z}
)^{ 1}
If f
is a Dirichlet character c,
the above is called a Dirichlet Lfunction :
L(c,z) =
S_{n}
c (n) n^{z}
=
P_{p}
( 1 
c (p) p^{z}
)^{ 1}
Such functions aren't limited to values of z 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(c_{1},z) =
(12^{z }) z(z)
and
L(c_{2},z) =
b(z)
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 Lfunctions can be expressed in terms of yet
another generalization of Riemann's zeta function,
known as the Hurwitz zeta function:
z(z,q) =
S_{n}
(n+q)^{z}
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 Lfunction for any Dirichlet character c
to the modulus k is simply a linear combination of Hurwitz zeta functions
(for rational values of q):
L(z,c) = k^{z}
_{k}
å
^{n=1}
c(n) z(z,n/k)
Conversely, the value (function of z) 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: