International Zhautykov Olympiad 2011 - Problem 5

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

International Zhautykov Olympiad 2011 - Problem 5

G H J

Reveal topic tags

greatest common divisor

modular arithmetic

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

31 posts

#1 h Jan 17, 2011, 7:47 AM • 2 Y

Y by Adventure10, Mango247

Let $n$ be integer, $n>1.$ An element of the set $M=\{ 1,2,3,\ldots,n^2-1\}$ is called good if there exists some element $b$ of $M$ such that $ab-b$ is divisible by $n^2.$ Furthermore, an element $a$ is called very good if $a^2-a$ is divisible by $n^2.$ Let $g$ denote the number of good elements in $M$ and $v$ denote the number of very good elements in $M.$ Prove that
$v^2+v \leq g \leq n^2-n.$

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#2 h Jan 17, 2011, 10:09 AM • 2 Y

Y by Adventure10, Mango247

1. Let us prove $g \leq n^2 - n$ . The number of elements $m \in M$ such that $\gcd(m,n^2) = 1$ is $\varphi(n^2) \geq n$ , since for $n = \prod_{k=1}^s p_k^{\alpha_k}$ , with $p_k$ primes and $\alpha_k \geq 1$ , we have $\varphi(n^2) = \prod_{k=1}^s (p_k -1) \cdot \prod_{k=1}^s p_k^{2\alpha_k - 1} \geq \prod_{k=1}^s p_k^{\alpha_k} = n$ . To these elements $m$ thus correspond at least $n-1$ elements $a = m+1 \in M$ (since $n^2-1$ is one of those elements $m$ , unavailable for $a$ ).
As $ab - b = b(a-1)$ , when $\gcd(a-1,n^2)=1$ we would need $n^2 \mid b$ in order to have $n^2 \mid ab - b$ , impossible since $1\leq b \leq n^2-1$ . Therefore the number of good elements is $g \leq (n^2-1) - (n-1) = n^2 -n$ (with equality reached for $n=2$ ).

Moreover, any time $\gcd(a-1,n^2)=d > 1$ , the element $a$ is good, since $b = n^2/d$ is then available, so in conclusion $a$ is good if and only if $\gcd(a-1,n^2) > 1$ .

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#3 h Jan 17, 2011, 6:15 PM • 2 Y

Y by Smoothy, Adventure10

2. Let $a$ be a very good element, so $n^2 \mid a^2 - a = a(a-1)$ . Since $\gcd(a,a-1) = 1$ , it follows that we must have $a=\alpha x^2$ and $a-1 = \beta y^2$ , with $\gcd(x,y) = 1$ , $n=xy$ (and also some other restrictions, which are irrelevant). Now assume another very good element $a'$ induces the representation $a'=\alpha' x^2$ and $a'-1 = \beta' y^2$ (using the same $x$ and $y$ ; if one of them is the same, then the other one needs also be the same).
Then $x^2 \mid a - a'$ and $y^2 \mid (a-1) - (a'-1) = a - a'$ , so $n^2 = x^2y^2 \mid |a-a'| < n^2$ , therefore $a=a'$ , contradiction. As a consequence, the representations of the very good elements $a$ use distinct $x$ 's and $y$ 's.

Let now $a_1,a_2,\ldots,a_v$ be the $v$ very good elements, with representations $a_k = \alpha_k x_k^2$ , indexed such that $1 < x_1 < x_2 < \cdots < x_v$ (we cannot have $x_1 = 1$ since that would imply $y_1 = n$ , and so $a_1 - 1 \geq n^2$ ; and we have seen that the $x_k$ need be distinct). It immediately follows $x_v \geq v+1$ .
But then, fixing $b = a_v = \alpha_vx_v^2$ , we may choose $a = 1 + \lambda y_v^2$ for all $1 \leq \lambda \leq x_v^2 - 1$ , since then $a \leq 1 + (x_v^2 - 1)y_v^2 < n^2$ . Moreover, we have $b(a-1) = \alpha_v \lambda x_v^2 y_v^2 = \alpha_v \lambda n^2$ , whence $n^2 \mid b(a-1)$ . It means all these $a$ 's are good, and there are $x_v^2 - 1 \geq (v+1)^2 - 1 = v^2 + 2v$ of them. This means $v^2 + 2v \leq g$ , an improvement on the bound asked (and even more maybe could be garnered by considering the other $a_k$ elements, for $1\leq k<v$ ).

This post has been edited 1 time. Last edited by mavropnevma, Jan 18, 2011, 7:21 AM

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#4 h Jan 18, 2011, 7:19 AM • 2 Y

Y by Adventure10, Mango247

A small correction (needed, since we may have the case with $v=1$ , $g=2$ , for example for $n=2$ , when $v^2 + v = g$ ). For an understandable reason (!?!), having reached the crux of the problem, I overlooked that in fact always $x_1 = 1$ , since for $a_1 = 1$ we have $n^2 \mid 1(1-1) = 0$ . The following fixes this oversight.

In general we have $v\geq 1$ ( $1$ is very good) and $g \geq 2$ ( $1$ and $n+1$ are good). For $v = 1$ therefore we have $v^2 + v \leq g$ (with equality actually occuring for $n=2$ , when $g=2$ ).
If $v>1$ , let us analyze when can we have (in the notations of above) $x_2=2$ , i.e. $a_2 = \alpha_2\cdot 4$ . This implies $n^2 \mid \alpha_2\beta_2 \cdot 4y_2^2$ , thus $n^2 = 4y_2^2$ , implying $n=2m$ ( $m = y_2$ ).
Then either $a_2 = m^2 + 1$ , with $4 \mid m^2+1$ , but then $4 \mid 3m^2 - 1$ , so $a = 3m^2 > a_2$ is very good, contradiction, or $a_2 = 3m^2 + 1$ , with $4 \mid 3m^2+1$ , but then $4 \mid m^2 - 1$ , so $1 < a = m^2 < a_2$ is very good, contradiction.
Therefore, when $v>1$ , we must have $x_2 > 2$ , therefore (by the reasoning in the above) $x_v \geq v+1$ , with the above proof leading to the conclusion $v^2 + v < v^2 + 2v \leq g$ .

Z K Y

The post below has been deleted. Click to close.

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

20 posts

Tiko93

#5 h Jan 28, 2011, 11:30 AM • 2 Y

Y by Adventure10, Mango247

We will prove that g=n^2-f(n^2),where f denotes Euler's totient function.
It is very easy to see that ab-b is div. by n^2( a,b are inM) <=>gcd(a-1,n^2)>1.Such that if gcd(a-1,n^2)=1=> b is div.by n^2,contradiction. And if gcd(a-1,n^2)=d>1,then we can take b=(n^2)/d<=(n^2)/2<=n^2-1 ,such that n>1.Thus b is in M and ab-b is div.by n^2.
Thus we get that g is the number of a's in M s.t. gcd(a-1,n^2)>1.And this number equals to g=(n^2-1)-(f(n^2)-1)=n^2-f(n^2) =n^2-n*f(n)<=n^2-n and equality holds if and only if n=2.
Let find the upper bound of v. if n=(product) p^a .a^2-a is div by n^2 implies that a=(u^2)*s ,and a-1=(v^2*t) ,with gcd (u,v)=1 ,n=uv, s is natural and t is nonnegative.s<v^2,and t<u^2.
Thus u =(prod1)p^a, v=(prod2)p^a ,where the set od prime divisors of u and don't intersect and their union is the set of prime divisors of n.
So we get that (u^2)*s-(v^2)*t=1,it has at most one solution in N,such that if there are 2 such solutions (s,t) and (p,q),then (u^2)*s-(v^2)*t=(u^2)*p-(v^2)*q=>(s-p) is div by v^2. which is impossible ,s.t 1<=s,p<v^2.
Such that for each factoring of n=uv ,we get at most one solution ,then the number of very good elements is at most the number of such factorings.If the number of prime factors of n is k,then we get that this number is 2^k-2.So v<=2^k-2
where v is the number of very good elements.
So v^2+v<=<4^k .
Let prove that g>=4^k).
Such that g=n^2-f(n^2)=n^2-nf(n)>=n^2-n(n-1)=n.
And let prove that n>=4^k.
The last one is true,because we can prove that only finitely many numbers don't satisfy to this inequality.For them we can calculate the value of g .This numbers are 2*3*5 and 2*3*7.

So g>=v^2+v.

This post has been edited 1 time. Last edited by Tiko93, Jan 28, 2011, 11:48 AM

Z K Y

The post below has been deleted. Click to close.

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

20 posts

Tiko93

#6 h Jan 28, 2011, 11:35 AM • 2 Y

Y by Adventure10, Mango247

More,we can prove that lim(v/g)=0

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#7 h Jan 28, 2011, 12:08 PM • 2 Y

Y by Adventure10 and 1 other user

Indeed, $g(n) = n^2 - \varphi(n^2)$ , where $\varphi$ is the Euler totient, while $v(n) = 2^{\omega(n)} -1$ , where $\omega$ is the arithmetic function counting the distinct primes dividing $n$ .

Z K Y

The post below has been deleted. Click to close.

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

14 posts

mmmath

#8 h Jun 21, 2011, 12:38 PM • 1 Y

Y by Adventure10

i want to prove that if $n=p_1^{a_1}....P_k^{a_k}$ Then $v=2^k-1$ and $g=n^{2}-\varphi(n^{2})$ then it's easy to prove the inequlity.
$x(x-1)\equiv 0\pmod{p^{2a_i}}$ so this equality have to roots so the equality $x(x-1)\equiv 0\pmod{n^2}$ have $2^k$ roots(by chinese remainder) but $n^2$ is one of the roots so $v=2^k-1$
so we can prove the inequality.

Z K Y

The post below has been deleted. Click to close.

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

1188 posts

#9 h Jan 3, 2022, 1:48 PM

Y by

Here is a solution, expanding upon mavropnevma's spoilers.

Regarding $n^2 \mid b(a-1)$ , if $\mbox{gcd}((a-1),n^2) = 1$ , then $n^2 \mid b$ , which is impossible for $1\leq b \leq n^2$ ; and if $\mbox{gcd}((a-1),n^2) = d>1$ , then picking $b=\frac{n^2}{d}$ works. Hence $g$ is equal to $n^2-1$ minus the number of integers in $\{0,1,\ldots,n^2-2\}$ coprime with $n^2$ , which is $n^2 - 1 - (\varphi(n^2) - 1) = n^2 - \varphi(n^2)$ , where $\varphi$ is the Euler totient. In particular $g\leq n^2 - n$ is equivalent to $\varphi(n^2) \geq n$ which is provable in many ways - either by proving $\varphi(p^{2k}) \geq p^k$ for prime $p$ or just observing that $kn-1$ , $k=1,2,\ldots,n$ are coprime with $n$ .

Regarding $n^2 \mid a^2 - a$ , let $n = \prod_{i=1}^k p_i^{\alpha_i}$ - we equivalently want $p_i^{2\alpha_i} \mid a(a-1)$ for all $i$ . As $a$ and $a-1$ are relatively prime, either $a\equiv 0 \pmod {p_i^{2\alpha_i}}$ or $a\equiv 1 \pmod {p_i^{2\alpha_i}}$ . So for each $i$ there are two choices for the remainder of $a$ - hence by the Chinese Remainder Theorem there are $2^k$ choices for $a$ modulo $n^2$ overall. As we have to exclude the possibility $a=0$ , we deduce $v = 2^k - 1$ and so $v^2 + v = 2^{2k} - 2^k$ .

To finish off, we will prove $4^k + \varphi(n^2) \leq n^2$ for $k\geq2$ (for $k=1$ we want $2+\varphi(n^2) \leq n^2$ which is true since $1$ and $n^2-1$ are coprime with $n^2$ ). Clearly $\varphi(n^2) \leq n^2-n$ (as multiples of $n$ are not coprime with $n$ ) and so if $n\geq 4^k$ we are done; this certainly holds when $3\nmid n$ , as then (recall that $n$ is odd) $n = \prod_{i=1}^k p_i^{\alpha_i} \geq 5^k$ . Now suppose $n=3^{\alpha}m$ and $m=\prod_{i=2}^k p_i^{\alpha_i}$ . Then we want $4^k + 2\cdot 3^{2\alpha-1}\varphi(m^2) \leq 3^{2\alpha}m^2$ - equivalently, $\frac{4^k}{3^{2\alpha}} + \frac{2}{3}\varphi(m^2) \leq m^2$ . With $\varphi(m^2) \leq m^2 - m$ we reduce to $\frac{4^k}{9} \leq \frac{m^2+2m}{3}$ , which follows by $m=\prod_{i=2}^k p_i^{\alpha_i} \geq 5^{k-1}$ .

This post has been edited 2 times. Last edited by Assassino9931, Jan 3, 2022, 1:50 PM

Z K Y

The post below has been deleted. Click to close.

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

58 posts

#10 h Jan 21, 2023, 6:39 PM

Y by

My solution (beautiful problem):
Consider a good number $a$ , there exists $b\in M$ which satisfies $n^2\;|\;b(a-1)$
If $(a-1,n^2)=1$ then $n^2\;|\;b$ (contradiction since $1\leq b\leq n^2-1$ )
So we must have $(a-1,n^2)>1$
If $(a-1,n^2)=d>1$ , choose $b=\frac{n^2}{d}$ then $n^2\;|\;b(a-1)$
So $a$ is good if and only if $(a-1,n^2)>1$
So we get the number of good numbers $a$ which is $n^2-1-(\varphi(n^2)-1)=n^2-\varphi(n^2)$
Notice that: $\varphi(n^2)=\displaystyle n^2\prod_{p\in\wp,p|n}\left(1-\frac{1}{p}\right)=n.n\prod_{p\in\wp,p|n}\left(1-\frac{1}{p}\right)=n\varphi(n)$
So we have $g=n^2-\varphi(n^2)=n^2-n\varphi(n)\leq n^2-n$
Consider the left inequality
Consider a very good number $a$
$p$ is a prime factor of $n$ , we have $p^{v_p(n^2)}\;|\;a(a-1)$
But $(a,a-1)=1$ so $p^{v_p(n^2)}\;|\;a$ or $p^{v_p(n^2)}\;|\;a-1$
If $p^{v_p(n^2)}\;|\;a$ for all $p|n$ then $n^2\;|\;a$ (contradiction since $1\leq a\leq n^2-1$ )
So we must have $a$ is very good if and only if for all prime factor $p$ of $n$ then $p^{v_p(n^2)}\;|\;a$ or $a-1$ , also there must exists a prime factor $p$ of $n$ such that $p^{v_p(n^2)}\;|\;a-1$
Call $r$ the number of distinct prime factor of $n$
We can evaluate $v=2^r-1$ (simple counting)
The problem becomes: Prove that $2^r(2^r-1)\leq n^2-\varphi(n^2)$
Induction on $r$ . For $r=1$ the problem is trivial
If the problem is true for some $r$ , then $2^r(2^r-1)\leq n^2-\varphi(n^2)$ , for all positive integer $n$ which have $r$ distinct prime factors
Consider a prime number $q$ with $(q,n)=1$
We need to prove that $2^{r+1}(2^{r+1}-1)\leq q^{2\alpha}n^2-\varphi(q^{2\alpha}n^2)$ with some $\alpha\in\mathbb Z^+$ , but it is true since
$q^{2\alpha}n^2\left(1-\prod_{p\in\wp,p|qn}\left(1-\frac{1}{p}\right)\right)\geq q^{2}n^2\left(1-\prod_{p\in\wp,p|qn}\left(1-\frac{1}{p}\right)\right)$
$=q^2n^2-\varphi(q^2n^2)$
$=q^2(n^2-\varphi(n^2))+q^2\varphi(n^2)-q(q-1)\varphi(n^2)$
$\geq q^2.2^r(2^r-1)+q\varphi(n^2)$
$\geq 4.2^r(2^r-1)+2n\varphi(n)$
$\geq 4.2^r(2^r-1)+2^{r+1}$ (since $n$ has $r$ distinct prime factors)
$=2^{r+1}(2^{r+1}-1)$
Combining the 2 inequalities we have $m^2+m\leq k\leq n^2-n$ , as desired
The equality happens, for example $n=2$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a