|
|
| Haga clic aquí para ver esta página en español. |
An Excess of Divisors
Submitted by Johannes Gerberding, 08 February 2001.
Original answer and this article by Allen Stenger.
How can you prove that the set of positive divisors of any (positive)
integer
n
contains at least as many elements ending with
1
or
9
as elements
ending with
3
or
7
?
For example, the divisors of
63
are
1, 3, 7, 9, 21, 63
;
so
3
divisors end with
1
or
9
,
and
3
divisors end with
3
or
7
.
For another example, the divisors of
441
are
1, 3, 7, 9, 21, 49, 63, 147, 441
;
so
5
divisors end with
1
or
9
,
and
4
divisors end with
3
or
7
.
Hint 1
One way to think about this problem is to count all the divisors with different weights:
Count those ending with
1
or
9
with weight
+1
,
those ending with
3
or
7
with weight
-1
,
and any other divisors with weight
0
.
Then we want to show the total weight is always
non-negative.
To formalize this, let's define a weight function:
If
d
is a divisor of
n
,
define
w(d) = +1
if
d
ends in
1
or
9,
define
w(d) = -1
if
d
ends in
3
or
7,
and
w(d) = 0
otherwise. Then we want to show
\sum_{d|n} w(d) \ge 0.
(Are we really any better off, or is this just empty formalism? We don't know yet,
but sums over all divisors are very widely used in number theory, so it is
a promising formalization.)
Hint 2
This problem is about factors and divisors, so it is natural to wonder if
it is possible to infer the value of
w(d)
from the values of
w
at the divisors of
d.
If so, we might hope to get some kind of recursive proof.
Try some examples; do you see any patterns?
Hint 3
Take for example
63 = 7 \cdot 9
.
The
w
values
are
w(63) = -1, w(7) = -1, w(9) = 1
,
and
w(63) = w(7) \cdot w(9)
.
Another example:
21 = 3 \cdot 7
.
The
w
values
are
w(21) = 1, w(3) = -1, w(7) = -1
,
and
w(21) = w(3) \cdot w(7)
.
See if you can prove in general that
w(r \cdot s) = w(r) \cdot w(s)
.
In number theory such functions are called "totally multiplicative".
Hint 4
This is proved by cases.
-
If
r
is even or divisible by
5
,
then
w(r) = 0
,
but also
r \cdot s
will be even or divisible by
5
and so
w(r \cdot s) = 0
.
-
If
r
and
s
both end in
1
or in
9
,
their product ends in
1
or
9
( 9 \cdot 9 = 81),
so
w(r \cdot s) = w(r) \cdot w(s)
in this case.
-
If
r
and
s
both end in
3
or
7
,
their product ends in
1
or
9
(3 \cdot 3 = 9, 3 \cdot 7 = 21),
so again
w(r \cdot s) = w(r) \cdot w(s)
.
-
If one of
r
and
s
ends in
1
or
9
with the other ending in
3
or
7
,
their product ends in
3
or
7
(
1 \cdot 3 = 3
,
1 \cdot 7 = 7
,
9 \cdot 3 = 27
,
9 \cdot 7 = 63),
so it is true in this case too.
This result implies that the
w
value can be calculated based on the prime
decomposition of the number; for example,
w(63) = w(3)^2 \cdot w(7)
.
Think about how to use this fact to write the sum over all divisors
in a different way, involving the prime divisors of
n.
Click here for rest of the solution.
The Rest of the Solution
The sum over all divisors can be written as a product over primes.
For example,
\begin{eqnarray}
\sum_{d|63} w(d) &=& w(1) + w(3) + w(7) + w(9) + w(21) + w(63) \\
&=& w(1) + w(3) + w(7) + w(3^2) + w(3 \cdot 7) + w(3^2 \cdot 7) \\
&=& \left( w(1) + w(3) + w(3^2) \right) \left( w(1) + w(7) \right).
\end{eqnarray}
And in general if
n = \prod_{p_i | n} p_i^{a_i},
then we have
\sum_{d|n} w(d) = \prod_{p_i | n} \left( w(1) + w(p_i) + \cdots + w(p_i^{a_i}) \right),
because each integer
d
has a unique factorization into primes.
Now we're nearly done! The key observation is that each term in
this product is non-negative.
Why? Because each
w(p_i)
is either
1
(and that sum is clearly positive) or
-1
(and that sum is either
1
or
0
,
depending on the number of terms,
and so is always non-negative), or
0
(that sum is
1
).
The whole product contains only non-negative terms, and so is non-negative.
Quadratic Residues
This proof doesn't explain the apparently special status of
1
and
9
compared to
3
and
7
.
Why are there more
1
and
9
divisors than
3
and
7
divisors
instead of the other way around, or instead of being random?
Because we are only looking at the last digit of each divisor, we
are essentially working modulo
10.
Working to a general modulus
m
we say that the number
n
is a
quadratic residue
modulo
m
if there is an integer
x
such that
x^2 \equiv n \pmod{m}
and if there is no such integer we say that
n
is a
quadratic nonresidue
modulo
m.
You can figure out all the quadratic residues just by forming
the squares of all numbers reduced to that modulus, and then
the nonresidues are anything left over; for example, modulo
10
the residues are
0, 1, 4, 5, 6, 9
and the nonresidues are the remaining classes,
2, 3, 7, 8.
One thing we notice is that our excess classes
1
and
9
are both quadratic residues while our other classes
3
and
7
are nonresidues. Coincidence?
The theory of quadratic residues modulo a prime is much nicer than
the theory for a general modulus, and most of the results are for
prime moduli. One very important property for a prime modulus
is that the product of any two residues or of any two nonresidues
is a residue, while the product of a residue and a nonresidue is
a nonresidue. This is exactly the property that we verified in Hint 4
for our weights!
It's true that
10
is not a prime, but its quadratic residue properties are almost
the same as they are for its prime divisor
5.
So the special status of divisors ending in
1
and
9
is that they are squares modulo
10.
References
-
You can read Johannes's original question
here.
-
Quadratic residues are discussed in nearly every general number theory
book, for example,
An Introduction to the Theory of Numbers
5th edition,
by G. H. Hardy and E. M. Wright, Oxford University Press, 1979,
Chapter 6,
and
Elementary Number Theory
by Edmund Landau, AMS Chelsea reprint, 1966,
Part I Chapter VI.
-
Wikipedia has an article on
quadratic residues.
|
