easy one

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

easy one

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: iran2004(number theory exam)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

793 posts

sam-n

#1 h Sep 11, 2004, 6:15 AM • 5 Y

Y by Adventure10, jhu08, Mango247, and 2 other users

We define $f: \mathbb{N} \rightarrow \mathbb{N}$ , $f(n) = \sum_{k = 1}^{n}(k,n)$ .

a) Show that if $\gcd(m,n)=1$ then we have $f(mn)=f(m)\cdot f(n)$ ;

b) Show that $\sum_{d|n}f(d) = nd(n)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7849 posts

#2 h Sep 11, 2004, 8:11 AM • 4 Y

Y by Adventure10, jhu08, Mango247, and 1 other user

a) We have $f(n)=\sum_{d|n}d\phi(\frac nd)$ , so $\frac{f(n)}n=\sum_{d|n}\frac{\phi(d)}d$ . It's a well-known fact that if $g$ is multiplicative, then so is $G(n)=\sum_{d|n}g(d)$ , and since $g(n)=\frac{\phi(n)}n$ is multiplicative, then so is $G(n)=\frac{f(n)}n$ , Q.E.D.

(by multiplicative I mean $f(mn)=f(m)f(n)$ whenever $(m,n)=1$ )

b) Since we have established the multiplicativity of $f$ , it's enough to show the conclusion holds for $n=p^k$ , with $p$ prime. $f(p^i),\ i\ge 1$ is, however, equal to $(i+1)p^i-ip^{i-1}$ . Now the conclusion follows easily (a very simple computation, since we have a telescopic sum).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

466 posts

#3 h Aug 23, 2021, 4:42 AM • 1 Y

Y by jhu08

sam-n wrote:

We define $f: \mathbb{N} \rightarrow \mathbb{N}$ , $f(n) = \sum_{k = 1}^{n}(k,n)$ .

a) Show that if $\gcd(m,n)=1$ then we have $f(mn)=f(m)\cdot f(n)$ ;

b) Show that $\sum_{d|n}f(d) = nd(n)$ .

Well we can see that any divisor $d$ of $n$ is repeated $\phi(\frac{n}{d})$ times , so
$f(n)=\sum_{d|n} id \times \phi (\frac{n}{d})=id \bigstar \phi$ where $\bigstar$ denotes the Dirichlet convolution.
After this everything follows serially

This post has been edited 1 time. Last edited by SPHS1234, Aug 23, 2021, 4:43 AM
Reason: Ec

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a