NT function debut

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

NT function debut

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Nepal Practice TST 3 P2 of 3; Own

The post below has been deleted. Click to close.

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

1008 posts

#1 h Apr 9, 2025, 3:53 PM • 1 Y

Y by khan.academy

Let $f$ be a function taking in positive integers and outputting nonnegative integers, defined as follows:
$f(m)$ is the number of positive integers $n$ with $n \le m$ such that the equation $an + bm = m^2 + n^2 + 1$ has an integer solution $(a, b)$ .
Find all positive integers $x$ such that $f(x) \ne 0$ and $f(f(x)) = f(x) - 1.$ (Adit Aggarwal, India.)

This post has been edited 1 time. Last edited by AshAuktober, Apr 10, 2025, 2:52 AM

Z K Y

The post below has been deleted. Click to close.

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

32 posts

Burmf

#2 h Apr 9, 2025, 4:12 PM

Y by

If $gcd(m,n) = d > 1$ , $d \mid m^2 + n^2 + 1$ . So $d$ has to be $1$ . By Bezout Theorem there always exist $a,b$ such that $an + bm = m^2 + n^2 + 1$ . So $f(m) = \phi(m)$ .
$\phi(\phi(x)) = \phi(x) -1$ . So $\phi(x)$ is a prime. $\phi$ is multiplicative and $\phi(x) > 1$ for $x > 2$ . So $x = 2p$ or $x = p$ . But then $p-1$ has to be prime so only solutions are $x = 6$ and $x = 3$

Z K Y

The post below has been deleted. Click to close.

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

1 post

#3 h Apr 9, 2025, 4:52 PM

Y by

@above
x=4 works too

Z K Y

The post below has been deleted. Click to close.

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

634 posts

#4 h Apr 9, 2025, 5:56 PM • 1 Y

Y by AshAuktober

Very nice problem!

Everyone enjoyed solving these

Z K Y

The post below has been deleted. Click to close.

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

1008 posts

#5 h Apr 10, 2025, 2:47 AM • 1 Y

Y by khan.academy

Here's the official solution I submitted:

Define $a' = a-n, b' = b-m$ , then we get the equation to be $a'n + b'm = 1$ , which has integer solution $(a', b')$ iff $gcd(m, n) = 1$ by Bezout's lemma. Therefore $f$ is nothing but the Euler Totient Function.
Now notice that the problem is asking when $f(x)$ is prime. Note that $x = 1$ doesn't work; therefore let $x = \prod_{i = 1}^k p_i^{a_i},$ where the $p_i$ are distinct primes and $a_i$ positive integers. (i. e. prime factorise $x$ ). As the Euler Totient Function is multiplicative, we can write $f(x)$ as $\prod_{i = 1}^k f\left(p_i^{a_i}\right)$ . Since this is prime, all but one of the $f(p_k^{a_k})$ evaluates to $1$ , while the last evaluates to a prime. Now $f(n) = 1$ iff $n \in \{1, 2\}$ (otherwise, take $1, n-1$ as two different numbers coprime to $n$ ).
Also $f(p_k^{a_k}) = p_k^{a_k-1}(p_k-1)$ by standard results, so for it to be prime, either $a_k = 1$ and $p_k-1$ is prime (yielding $p_k = 3$ ), or $a_k = 2$ , $p_k-1 = 1$ i. e. $p_k^{a_k} = 4$ . If the prime $f(p_k^{a_k})$ is $f(3)$ , then we multiply either 1 or 2 with it to get the results $x = 3, 6$ . If it's $f(4)$ , we can't multiply 2, so the only result from this case is $x = 4$ .
Therefore, the solution set is $\{3, 4, 6\}$ and since all of these values work, we are done.

Z K Y

The post below has been deleted. Click to close.

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

SimplisticFormulas

120 posts

SimplisticFormulas

#6 h Apr 12, 2025, 10:50 AM

Y by

very nice congrats on getting first problem accepted into a contest

Z K Y

The post below has been deleted. Click to close.

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

55 posts

#7 h Apr 12, 2025, 1:53 PM

Y by

Suppose $(m,n)=d>1$ . So that: $d \mid an+bm-m^2-n^2 \mid 1$ (contradiction)
Therefore, $(m,n)=1$ . By bezout theorem, there exist $a,b \in \mathbb{Z}$ such that $an+bm=m^2+n^2+1$
So that for each fixed $m$ , every number $n<m$ such that $(m,n)=1$ is satisfy
This give $\phi (n) =f(n)$ .
We have: $\phi\left( \phi(n)\right)= \phi (n) -1$ .
Because $\phi (n)\le n-1$ , so $\phi(n)$ is a prime number.
Let $n =p_1^{\alpha_1}....p_k^{\alpha_k} \left(\alpha_i>0, \forall 1 \le i \le k\right)$
Then $\phi(n) = p_1^{\alpha_1-1}\left(p_1-1\right)....p_k^{\alpha_k-1}\left(p_k-1\right)$ is a prime number, which give us $n=p$ or $2p$ with $p$ is a prime number
+) If $n=p$ then $\phi (p-1) =p-2$ , easy to see that $p=3$ .
+) If $n=2p$ :
$n=4$ is work
If $p>2$ then similar to $n=p$ , we have $p=3$ , give $n=6$
All solution to this problem are $\boxed {3,4,6}$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a