Period of function (Izho)

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

Period of function (Izho)

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Izho

The post below has been deleted. Click to close.

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

97 posts

#1 h Jan 12, 2019, 11:55 AM • 4 Y

Y by Davrbek, Mathuzb, Adventure10, Mango247

Natural number $n>1$ is given. Let $I$ be a set of integers that are relatively prime to $n$ . Define the function $f:I=>N$ . We call a function $k-periodic$ if for any $a,b$ , $f(a)=f(b)$ whenever $k|a-b$ . We know that $f$ is $n-periodic$ . Prove that minimal period of $f$ divides all other periods.
Example: if $n=6$ and $f(1)=f(5)$ then minimal period is 1, if $f(1)$ is not equal to $f(5)$ then minimal period is 3.

Z K Y

The post below has been deleted. Click to close.

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

1400 posts

#2 h Jan 12, 2019, 7:19 PM • 1 Y

Y by Adventure10

Nice problem. I will first give some motivation. Inspect small cases (such as $n=12$ or $8$ ), with 'smallest' periods $q$ , that possibly don't divide $n$ (could be coprime or not). You'll realize that, if you let $d=(q,n)>1$ , then $d$ will turn out to be a period, contradicting with minimality of $q$ , as $q\nmid n$ , $d<q$ .

Motivated by this, suppose that $n'$ is any period of this function, and $q$ is the smallest period. Suppose $n'=dn_1$ and $q=dq_1$ , where $d=(n',q)<q$ . I will establish that, $d\mid a-b\implies f(a)=f(b)$ , and thus, $d$ is also a period, contradicting with minimality of $q$ . To that end, take two numbers, $a_1\equiv a_2\pmod{d}$ . I claim that, there exists a $k$ , such that $a_1+kq \equiv a_2\pmod{n'}$ . For this $k$ , the fact that $q$ is a period implies $f(a_1)=f(a_1+kq)$ , and the fact that $a_1+kq\equiv a_2\pmod{n'}$ implies $f(a_1+kq)=f(a_2)=f(a_1)$ , using the fact that $n'$ is also a period.

Now, suppose $a_1-a_2 = \ell d$ for some $\ell\in\mathbb{Z}$ . Note that, $a_1+kq\equiv a_2 \pmod{dn_1} \iff \ell d+kdq_1 \equiv 0\pmod{dn_1}$ , which holds, if we establish existence of a $k_1$ , so that $\ell + kq_1 \equiv 0\pmod{n_1}$ . But since $(q_1,n_1)=1$ , $q_1^{-1}$ in modulo $n_1$ exists, and thus, it suffices to take, $k\equiv -\ell q_1^{-1}\pmod{n_1}$ .

Therefore, we are done.

This post has been edited 1 time. Last edited by grupyorum, Jan 12, 2019, 7:24 PM

Z K Y

The post below has been deleted. Click to close.

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

125 posts

#3 h Jan 13, 2019, 7:32 PM • 1 Y

Y by Adventure10

Quote:

Nice problem. I will first give some motivation. Inspect small cases (such as $n=12$ or $8$ ), with 'smallest' periods $q$ , that possibly don't divide $n$ (could be coprime or not). You'll realize that, if you let $d=(q,n)>1$ , then $d$ will turn out to be a period, contradicting with minimality of $q$ , as $q\nmid n$ , $d<q$ .

Motivated by this, suppose that $n'$ is any period of this function, and $q$ is the smallest period. Suppose $n'=dn_1$ and $q=dq_1$ , where $d=(n',q)<q$ . I will establish that, $d\mid a-b\implies f(a)=f(b)$ , and thus, $d$ is also a period, contradicting with minimality of $q$ . To that end, take two numbers, $a_1\equiv a_2\pmod{d}$ . I claim that, there exists a $k$ , such that $a_1+kq \equiv a_2\pmod{n'}$ . For this $k$ , the fact that $q$ is a period implies $f(a_1)=f(a_1+kq)$ , and the fact that $a_1+kq\equiv a_2\pmod{n'}$ implies $f(a_1+kq)=f(a_2)=f(a_1)$ , using the fact that $n'$ is also a period.

Now, suppose $a_1-a_2 = \ell d$ for some $\ell\in\mathbb{Z}$ . Note that, $a_1+kq\equiv a_2 \pmod{dn_1} \iff \ell d+kdq_1 \equiv 0\pmod{dn_1}$ , which holds, if we establish existence of a $k_1$ , so that $\ell + kq_1 \equiv 0\pmod{n_1}$ . But since $(q_1,n_1)=1$ , $q_1^{-1}$ in modulo $n_1$ exists, and thus, it suffices to take, $k\equiv -\ell q_1^{-1}\pmod{n_1}$ .

Therefore, we are done.

Actually you have to show that for any $d|a_1-a_2$ there is $dn_1|a_1+kq-a_2$ and $(a_1+kq,n)=1$

Z K Y

The post below has been deleted. Click to close.

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

mohammad14101381

16 posts

mohammad14101381

#4 h Jan 14, 2019, 4:37 PM • 2 Y

Y by Adventure10, Mango247

grupyorum wrote:

Nice problem. I will first give some motivation. Inspect small cases (such as $n=12$ or $8$ ), with 'smallest' periods $q$ , that possibly don't divide $n$ (could be coprime or not). You'll realize that, if you let $d=(q,n)>1$ , then $d$ will turn out to be a period, contradicting with minimality of $q$ , as $q\nmid n$ , $d<q$ .

Motivated by this, suppose that $n'$ is any period of this function, and $q$ is the smallest period. Suppose $n'=dn_1$ and $q=dq_1$ , where $d=(n',q)<q$ . I will establish that, $d\mid a-b\implies f(a)=f(b)$ , and thus, $d$ is also a period, contradicting with minimality of $q$ . To that end, take two numbers, $a_1\equiv a_2\pmod{d}$ . I claim that, there exists a $k$ , such that $a_1+kq \equiv a_2\pmod{n'}$ . For this $k$ , the fact that $q$ is a period implies $f(a_1)=f(a_1+kq)$ , and the fact that $a_1+kq\equiv a_2\pmod{n'}$ implies $f(a_1+kq)=f(a_2)=f(a_1)$ , using the fact that $n'$ is also a period.

Now, suppose $a_1-a_2 = \ell d$ for some $\ell\in\mathbb{Z}$ . Note that, $a_1+kq\equiv a_2 \pmod{dn_1} \iff \ell d+kdq_1 \equiv 0\pmod{dn_1}$ , which holds, if we establish existence of a $k_1$ , so that $\ell + kq_1 \equiv 0\pmod{n_1}$ . But since $(q_1,n_1)=1$ , $q_1^{-1}$ in modulo $n_1$ exists, and thus, it suffices to take, $k\equiv -\ell q_1^{-1}\pmod{n_1}$ .

Therefore, we are done.

I think this solution is imperfect
Because you need this property for K too:

(n,a1+kq)=1

Z K Y

The post below has been deleted. Click to close.

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

1400 posts

#5 h Jan 14, 2019, 4:40 PM • 2 Y

Y by Adventure10, Mango247

Guys, I agree with both. Yes, my argument requires a fix, not sure benign or malign. I don't have right now time to try to fix the argument, but you are welcome to do so.

Z K Y

The post below has been deleted. Click to close.

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

7 posts

Asjmaj

#6 h Jan 1, 2021, 9:20 AM • 1 Y

Y by Mango247

Bump. Not sure if the argument above can be fixed

Z K Y

The post below has been deleted. Click to close.

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

343 posts

#7 h Jan 2, 2021, 3:35 PM

Y by

It's strange that there is no solution to this problem in the official solution. :maybe:

:maybe:

Z K Y

The post below has been deleted. Click to close.

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

1193 posts

#8 h Dec 31, 2021, 3:18 PM

Y by

Here is a complete solution (rephrased from a StackExchange post by Bart Michels):

Let $p$ be the minimal period and suppose, for contradiction, that $p$ does not divide $n$ . We can then write $n=pq+r$ for some $1 \leq r \leq p-1$ . We claim that $r$ must also be a period. To show this, take any $a$ and $b$ coprime with $n$ such that $r\mid a-b$ (if there are
no such, i.e. $r\nmid a-b$ always holds, we are done). Then with $a-b=sr$ for some $s$ we obtain $a-b = sn - spq$ . Noting that $b$ , $a=b+sn-spq$ and hence $b+sn$ are all coprime with $n$ , we obtain $f(a) = f(b+sn-spq) = f(b+sn) = f(b)$ (the second equality is because $p$ is a period and the last is because $n$ is a period) - therefore $r$ is also a period, thus contradicting the minimality of $p$ . Therefore $p$ divides $n$ . What is more, in exactly the same manner (by applying Euclid's algorithm) we have that if $n_0$ is a period, then $\mbox{gcd}(n_0,n)$ is also a period.

Now let $k$ be any other period - the problem requires us to prove $p\mid k$ . If $k$ does not divide $n$ , then by the end of the previous paragraph we may work with $\mbox{gcd}(n,k)$ - and if we show $p\mid \mbox{gcd}(n,k)$ we will also have $p\mid k$ by $\mbox{gcd}(n,k)\mid k$ . Hence we may assume that $p$ and $k$ divide $n$ . Our aim is to show that $d := \mbox{gcd}(p,k)$ also must be a period - then by the minimality of $p$ we shall have $\mbox{gcd}(p,k) = p$ and we will be done.

So let $x$ and $y$ coprime to $n$ be such that $y-x = td$ for some $t$ . Then by Bezout's Lemma the inverse $x^{-1} \pmod n$ exists and we have for ANY $u$ and $v$ that $f(x) = f(x + pux) = f((1+pu)x) = f((1+pu)x + kv(1+pu)x) = f((1+pu)(1+kv)x)$ and $f(y) = f(x + td) = f((1 + tdx^{-1})x)$ . Since $f$ is $n$ periodic, we will be done if we show that regardless of $t_0 := tx^{-1}$ we can pick $u$ and $v$ such that $1+t_0d \equiv (1+pu)(1+kv) \pmod n$ .

By the Chinese remainder theorem, it suffices to show that we can find such $u$ and $v$ modulo each maximal prime power divisor $q^s$ of $n$ . Fix $q^s$ , and let $x,y,z$ be the exponents of $q$ in $p,k,d$ . Then $z = \min(x, y)$ . By symmetry, we may assume $z = x$ . Write $d = q^x \delta$ , $p = q^x\alpha$ with $\gcd(\alpha\delta, q) = 1$ and let $\alpha^{-1} \in \mathbb Z$ be an inverse of $\alpha$ mod $q^s$ . Then we can take $u = t_0\delta\alpha^{-1}$ and $v = 0$ . Indeed: $1 + td = 1 + t \delta q^x \equiv 1+t\delta \alpha^{-1}\alpha q^x \pmod{q^s} = (1+ua)(1+vb)$ , as desired.

This post has been edited 4 times. Last edited by Assassino9931, Jan 1, 2022, 9:11 PM

Z K Y

The post below has been deleted. Click to close.

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

30627 posts

#9 h Dec 31, 2021, 9:45 PM

Y by

Rickyminer wrote:

It's strange that there is no solution to this problem in the official solution. :maybe:

:maybe:

even in Russian the official solution is empty

according to the official results, 5 /95 contestants solved it fully (7/7) (2 from Mongolia and 3 from Bulgaria)

This post has been edited 1 time. Last edited by parmenides51, Dec 31, 2021, 9:50 PM

Z K Y

The post below has been deleted. Click to close.

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

1193 posts

#10 h Jan 2, 2022, 6:19 PM

Y by

See http://matol.kz/comments/4119/show for a quicker (and I think correct) solution.

Z K Y

The post below has been deleted. Click to close.

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

892 posts

#12 h Jan 23, 2023, 9:21 AM • 1 Y

Y by pokpokben

Let $a$ and $b$ be two periods. Then for $(a,b)|a_i-a_j$ one can find natural $x,y$ such that $ax+a_j=by+a_i$ . Thus $f(ax+a_j-by)=f(a_i) \implies f(a_j)=f(a_i)$ . So $(a,b)$ is also a period and 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.

shafikbara48593762

17 posts

shafikbara48593762

#13 h Feb 2, 2025, 4:09 AM

Y by

From Bezout we know:
we can find integers $k$ and $t$ such that $km+tn=gcd(m,n)$

Let m be any period and let r be the minimum period
And $km+tr=gcd(m,r)$
$f(x) = f(x+zm)$ $f(x) = f(x+zr)$ for any z
And from the lemma $f(x)=f(x+km-tr)=f(x+gcd(m,r))$
And from the minimality we get $r|m$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a