Lesson 15: Number Theoretic Functions B
Adithya B., Brian L., William W., Daniel X.
October 2020
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 1 / 14
General Functions
Often, we are presented with a newly defined number theoretic
function and asked to work with it
On such problems, we have no prior knowledge about the function,
unlike say the totient function
Instead, it’s important to understand how the function behaves to
supplant this lack of prior knowledge
In the examples, we’ll discover a lot about our function before we
extract the final answer
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 2 / 14
General Functions
2014 AIME II # 15
For any integer k ≥ 1, let p(k) be the smallest prime which does not
divide k. Define the integer function X (k) to be the product of all primes
less than p(k) if p(k) > 2, and X (k) = 1 if p(k) = 2. Let {xn } be the
sequence defined by x0 = 1, and xn+1 X (xn ) = xn p(xn ) for n ≥ 0. Find the
smallest positive integer, t such that xt = 2090.
xn p(xn )
We have the recursion xn+1 = X (xn )
How to interpret this?
Given xn , multiply by the smallest prime not dividing xn and divide by
all smaller primes
So considering the prime factorization of xn will be useful
Let’s write out the first few xi :
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 3 / 14
2014 AIME II # 15
x0 = 1, x1 = 2
x2 = 3
x3 = 6 = 2 · 3
x4 = 5
x5 = 10 = 2 · 5
x6 = 15 = 3 · 5
x7 = 30 = 2 · 3 · 5
x8 = 7
Considering the prime factorization, we find the smallest prime not in
it, add it, and delete all smaller primes.
In particular, this looks a lot like binary!
We can rewrite the first few xi to see this more clearly
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 4 / 14
2014 AIME II # 15
x1 = 70 · 50 · 30 · 21
x2 = 70 · 50 · 31 · 20
x3 = 70 · 50 · 31 · 21
x4 = 70 · 51 · 30 · 20
x5 = 70 · 51 · 30 · 21
x6 = 70 · 51 · 31 · 20
x7 = 70 · 51 · 31 · 21
x8 = 71 · 50 · 30 · 20
So if ek ek−1 · · · e0 is the binary representation of n then
ek−1
xn = pkek pk−1 · · · p0e0 (where p1 < p2 < · · · is the sequence of primes)
We can rigorously prove this, but it is just a formalization of this
intuition
To get xn+1 we find the first zero in the above, flip it to a 1, and
change everything after it to a 0, equivalent to adding 1 in binary
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 5 / 14
2014 AIME II # 15
Now we can extract the answer
xt = 2090 = 2 · 5 · 11 · 19
191 · 170 · 130 · 111 · 70 · 51 · 30 · 21
100101012 = 149
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 6 / 14
General Functions
2013 AIME II # 14
For positive integers n and k, let f (n, k) be the remainder when n is
divided by k, and for n > 1 let F (n) = maxn f (n, k). Find the remainder
1≤k≤ 2
100
X
when F (n) is divided by 1000.
n=20
Our main task is to understand the function F for 20 ≤ n ≤ 100
Given n, which k should we choose to maximize f (n, k)?
We want the largest multiple of k less than n to be far from n
Equivalently, we want the smallest multiple of k more than n to be
close to n
We should choose a k such that ki > n but (k − 1)i ≤ n for some
integer i; otherwise k + 1 would be a better choice
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 7 / 14
2013 AIME II # 14
n
n
This works out to k − 1 ≤ i < k, or k = i +1
n
Since 1 ≤ k ≤ 2 we need i ≥ 3
Then
f (n, k) = n − (i − 1)k = n − (i − 1)( ni + 1) = ni − (i − 1 − n mod i)
Now, note that this is roughly ni , so minimizing i will, in general, give
a larger value of f (n, k)
Because we have n ≥ 20, the difference between n3 and n4 is greater
than the other differences, so it will always be better to take i = 3.
Now, we just need to sum f (n, n3 + 1) = n3 − (2 − n mod 3) over
all n.
Computation of this gives us
3( 7+33
2 )(33 − 7 + 1) − 27 − 27(0 + 1 + 2) = 1512, so our answer is
512 .
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 8 / 14
Totient Function
Recall that the totient function returns the number of integers in
{1, 2, . . . , n} that are relatively prime to n
We denote this as ϕ(n)
If p1 , p2 , . . . , pk are the distinct primes dividing n, then we have the
following formula:
ϕ(n) = 1 − p11 1 − p12 · · · 1 − p1k n
This can be proved using PIE and a little bit of factoring; try it on
your own if you haven’t seen it before
The totient function has many nice properties stemming from both its
definition and this formula, such as Euler’s Theorem: if gcd(a, n) = 1
then aϕ(n) ≡ 1 (mod n)
Let’s see some of them in the following examples
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 9 / 14
Totient Function
Classical
Let n be a positive integer. Prove that
X jnk 1
ϕ(k) = n(n + 1).
k 2
k≥1
Let’s try induction!
Let f (n) be equal to the sum in the problem. What is
f (n) − f (n − 1)?
ϕ(k) kn − n−1
P
f (n) − f (n − 1) = k
k≥1
What exactly is the difference of floors? Remember bn/kc counts the
number of multiples of k at most n.
It is nonzero when k | n.
P
Therefore, f (n) − f (n − 1) = φ(k). What is this sum?
k|n
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 10 / 14
Totient Function
Lemma
P
k|n φ(k) = n
Proof.
Consider the fractions n1 , n2 , . . . , nn in reduced form.
How many fractions have a denominator of k?
If there was a fraction of the form ka , then we must have
gcd(a, k) = 1 for it to be in simplest form. Therefore, there are φ(k)
possible values of a.
Every such fraction is included exactly once, so there are φ(k)
P
Since there are n fractions in total, k|n φ(k) = n
As f (n) − f (n − 1) = n for all n and f (1) = 1, we can easily show
with induction that f (n) = 21 n(n + 1).
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 11 / 14
Totient Function
TST 2018 #1
Let n ≥ 2 be a positive integer, and let σ(n) denote the sum of the
positive divisors of n. Prove that the nth smallest positive integer relatively
prime to n is at least σ(n), and determine for which n equality holds.
Suppose the divisors of n are d1 , d2 , . . . , dk . We care about the
interval [1, d1 + d2 + · · · + dk ].
A single interval of size d1 + d2 + · · · + dk is quite awkward.
Note that k intervals of sizes d1 , d2 , . . . , dk are much simpler
How many numbers relatively prime to n are there in an interval
[m, m + di )?
This ranges over all residues mod di , so there are exactly φ(di )
relatively prime to di , so at most φ(di ) relatively prime to n
Now, summing this over all intervals gives us ki=1 ϕ(di ) = n.
P
Thus, there are at most n values in the whole interval of size σ(n)
that are relatively prime to n.
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 12 / 14
TST 2018 #1
Thus, the nth smallest value relatively prime to n is at least σ(n),
since there are at most n values up to that point.
Now, we claim that equality only holds for n equal to a prime power.
First, for prime power n = p α , what’s its divisor sum? What’s the nth
smallest number relatively prime with it?
α+1
σ(n) = 1 + p + . . . + p α = p p−1−1 . For the latter, note that there are
(p − 1)m numbers relatively prime to p α less than pm
p α+1 −p
So, there are p α − 1 numbers rel prime to n less than p−1 , so our
answer is
p α+1 − p p α+1 − 1
+1= = σ(n)
p−1 p−1
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 13 / 14
TST 2018 #1
For n not a prime power, suppose we have distinct primes p, q such
that pq|n.
WLOG, assume p < q.
If we were to make our first interval of size q, there would be a value
in that interval relatively prime with the interval size but not relatively
prime with n (in particular, p).
Thus, equality cannot hold.
Adithya B., Brian L., William W., Daniel X. Lesson 15: Number Theoretic Functions B October 2020 14 / 14
