Let $p \ge 5$ be a prime number. For a positive integer $k$, let $R(k)$ be the remainder when $k$ is divided by $p$, with $0 \le R(k) \le p-1$. Determine all positive integers $a < p$ such that, for every $m = 1, 2, \cdots, p-1$, $$ m + R(ma) > a. $$
Problem
Source: RMM 2015 Problem 5
Tags: RMM, number theory, prime numbers
01.03.2015 15:59
Think it is all numbers such that a is a divisor of p-1, but have no idea how to prove this thing.
01.03.2015 20:06
Actually, the answer happens to be $a = \left\lfloor \frac{p-1}{n} \right\rfloor$ $\forall n \in [1, p-1]$. First, we show that each $a$ which does not divide $p-1$ is of this form. Suppose that $a \nmid p-1$. Let \[\frac{p-1}{n} < a = \frac{p-1}{n}+k \le \frac{p-1}{n-1}\]. Note that $k \le \frac{p-1}{n(n-1)}$. Taking $m = n$, we have $R(ma) = nk-1 > n-a$. Regrouping stuff, we get \[k > \frac{p-1}{n(n-1)}-1 \implies a > \frac{p-1}{n-1}-1 \]Therefore, from our assumption on the bounds of $a$, we must have $a = \left\lfloor \frac{p-1}{n-1} \right\rfloor$.
Hence, the only solutions are $a = \left\lfloor \frac{p-1}{n} \right\rfloor$ $\forall n \in [1,p-1]$.
01.03.2015 20:10
FIrst, we will prove that all numbers of the form $\left\lfloor\dfrac{p}{q}\right\rfloor$ and $p-1$ verify, where $q$ runs from $2$ to $p$. It is trivial why $p-1$ verifies so let us take a number $a$ of the form $\left\lfloor\dfrac{p}{q}\right\rfloor$ and prove our assertion. Let $p=q\cdot c + r_1$ with $0\le r_1\le q-1$. Now, take the number $m$ as in the statement. Obviously, we can and will assume that $m\le \left\lfloor\dfrac{p}{q}\right\rfloor.$ Write $m$ in the form $q\cdot d + r_2$ with $0\le r_2\le q_1$. Now we have to prove that $$R\left(m\cdot \left\lfloor\dfrac{p}{q}\right\rfloor\right)> \left\lfloor\dfrac{p}{q}\right\rfloor-m $$ and this rewrites as $$R(cr_2-dr_1)> c-qd-r_2.$$ If $r_2=0$, the inequality is obvious and if $r_2\neq 0$, then $R(cr_2-dr_1)=cr_2-dr_1$ and it is enough to prove that $dr_1<qd+r_2$ which is true since $r_1<q$. Thus, we proved that the numbers of this form verifies, now we will prove that those are the only ones. Well, this is the part i managed to solve in the contest, even if the problem was not that hard. We will take $a>\lfloor\sqrt{p}\rfloor$(which verifies the hypothesis) because otherwise is trivial. Take $m$ such that $$am<p<a(m+1).$$ Then, we have that $$a(m+1)-p>a-m-1\Leftrightarrow m(a+1)\ge p.$$ Thus, we got $\dfrac{p}{m}>a>\dfrac{p}{m}-1$ and this means that $a$ is of the form $\left\lfloor\dfrac{p}{m}\right\rfloor$ and the proof ends.$\blacksquare$
01.03.2015 23:50
02.03.2015 08:59
Well I have to say that this was not a "NUMBER THEORY" in the hardcore sense.Anyways,the solution: First I show that the numbers are necessarily of the form $\lfloor\frac{p}{m}\rfloor$. Let $a$ be a number of required type.There is a mimimum $t$ such that $p \le ta <2p$ Now apply the condition for $m=t$ .Let $ta=p+r$ where $0 \le r<p-1$.By condition $r >a-t$ and hence $p<ta-a+t$ .Now rearrange this to get $(t-1)a+t \ge p+1$ or $a \ge \frac{p}{t-1}-1$.But by minimality of $t$ we have $a<\frac{p}{t-1}$.As $a$ is an integer,it must be $\lfloor\frac{p}{t-1} \rfloor$. Now the sufficient condition.Let $a=\lfloor\frac{p}{m}\rfloor$ and $p=am+r_1$ with $0 \le r_1 \le m-1$.And now take any $m$and let $n=tm+r_2$ where $0 \le r_2 \le m-1$..Hence $na=tma+r_2a=tma+tr_1-tr_1+ar_2$.Clearly $p|tma+tr_1$ Hence $R(na)=R(ar_2-tr_1)$.What we have to prove is $R(ar_2-tr_1)>a-tm-r_2$.Now we prove $-p<ar_2-tr_1<p$. Notice that it is sufficient to consider $m\le a$ cases.Hence $a \ge tm+r_2$.and hence $a >t-1$.Again we have $m>r_1$ and hence $m+r_2>r_1$.Thus we have $a(m+r_2)>r_1(t-1)$ and rearranging this we get $ar_2-tr_1<-p$.Again clearly $r_2-m <0$ and hence $a(r_2-m)<tr_1+r_1$ and thus $ar_2-tr_1<p$. Thus $R(ar_2-tr_1)=ar_2-tr_1$ or $p-ar_2+tr_1$.Now $ar_2-tr_1<a-tm-r_2$ it is straight forward.If $R(ar_2-tr_1)=p-ar_2+tr_1$,then $R(ar_2-tr_1)-a+tm+r_2=a(r_2+1-m)-t(r_1+m)-r_2$ and as $r_2+1 \le m$,R.H.S is less than $0$.Hence then also $R(ar_2-tr_1)>a-tm-r_2$.Hence we are done. HUH!! :O I am sure that the sufficient part is not this tedious and also I must have made some mistakes in these inequality part but my only consolation is:THEY MUST BE EASILY FIXABLE. Also another thing :I request that someone please add this and also,if possible,the 2014 questions of RMM in the contests page section because with this new AoPS,it is really hard to search the forums and find these problems. :\
13.03.2015 20:19
mathdebam wrote: Also another thing :I request that someone please add this and also,if possible,the 2014 questions of RMM in the contests page section because with this new AoPS,it is really hard to search the forums and find these problems. :\ I do believe there was not a RMM 2014 due to funding issues. By the way, your solution looks great !
14.08.2015 01:39
We'll prove that $a$ satisfies the problem statement iff its of the form $\left\lfloor\frac{p - 1}{n}\right\rfloor$ for some $n \in \{1, 2, \cdots , p - 1\}.$ Fix some $a$, and by the Division Algorithm, write $p = aq + r$ for integers $q, r$ with $0 \le r < a$ and $1 \le q \le p.$ We claim that $a$ satisfies the problem statement iff $q \ge r.$ First, suppose that $q < r.$ Take $m = q + 1$ so that $ma = p + (a - r).$ It is clear that $p < ma < 2p$, so that $R(ma) = a - r.$ Hence, $m + R(ma) = (q + 1 - r) + a \le a$, implying that $a$ does not satisfy the problem statement. Conversely, suppose that $q \ge r.$ By the Division Algorithm, write $m = bq + s$ for integers $b, s$ with $0 \le s < q.$ Hence, $ma = bp + as - br.$ Note that $as - br \le as < aq \le p.$ Therefore, $R(ma) \ge as - br$, which implies that $m + R(ma) \ge b(q - r) + s(a + 1).$ If $s \ge 1$, it is clear that this quantity is strictly greater than $a.$ Meanwhile, if $s = 0$, then note that $br \le bq = m < p.$ Hence, $R(ma) = R(bp - br) = p - br.$ It follows that $m + R(ma) = p + b(q - r) > a$ as desired. Now to finish, we will prove that $q \ge r$ iff $a$ is of the form $\left\lfloor\frac{p - 1}{n}\right\rfloor$ for some $n \in \{1, 2, \cdots , p - 1\}.$ First, suppose that $q \ge r.$ If $r = 0$, then $a = 1$, so we may take $n = p - 1.$ Otherwise, write $a = \frac{p - 1 + (1 - r)}{q} = \left\lfloor\frac{p - 1}{q}\right\rfloor.$ Now, suppose that $a = \left\lfloor\frac{p - 1}{q}\right\rfloor.$ If $q = 1$, then the desired result is clear. Otherwise, since $p$ is prime, $\left\lfloor\frac{p - 1}{q}\right\rfloor = \left\lfloor\frac{p}{q}\right\rfloor.$ Therefore, we may write $p = aq + r$ for integer $r$ with $0 \le r < a.$ It follows that $\frac{p - 1}{q} = a + \frac{r - 1}{q} < a + 1.$ Thus we obtain $q \ge r$, as desired. $\square$
08.02.2016 13:49
We claim that the answer is all positive integers of the form $\left\lfloor\frac{p-1}{n}\right\rfloor$ for some positive integer $n$. Let $p=an+k$, where $0<k<a$. Taking $m=\frac{p+a-k}{a}$, we have that $n+1+a-k>a$, so $n+1>k$, which means that $n\geq k$. Now, $an<p\leq an+n=n(a+1)$, so $an-1<p-1\leq(a+1)n-1$, or $an\leq p-1<(a+1)n$. This rearranges to $a\leq\frac{p-1}{n}<a+1$, which means that $\left\lfloor\frac{p-1}{n}\right\rfloor=a$, proving that for all $a$ that work there exists some integer $n$ with $\left\lfloor\frac{p-1}{n}\right\rfloor=a$. Now it remains to show that $a=\left\lfloor\frac{p-1}{n}\right\rfloor$ works for all $n$. It only suffices to consider $m<a$, because otherwise $m+R(ma)$ is trivially greater than $a$. Similarly, it only suffices to consider $R(ma)<a$. If $n=1$, then $a=p-1$, so $R(ma)=p-m$, and we clearly have $m+p-m>a=p-1$. Now, suppose that $n>1$. Then, $a=\left\lfloor\frac{p}{n}\right\rfloor$, so if $p=an+k$ where $a>k$ then $n>k$ as well. The smallest positive integer $m$ with $R(am)<a$ is $m=n+1$. In this case, $R(am)=a-k$, but we have that $m+R(am)=n+1+a-k>a$. The next time this occurs is either $m=2n+1$, in which case $R(am)=2(a-k)$ and $m+R(am)=2n+1+2a-2k>a$, or $m=2n$, in which case $R(am)=a-2k$ and $m+R(am)=2n+a-2k>a$. In general, the $i$-th time this occurs is $in\leq m\leq i(n+1)$. When that happens, we have that $m+R(am)\geq in+a-ik>a$, as desired.
10.02.2016 08:17
Actual solution: Obviously claim answer $\lfloor \frac{p-1}{n} \rfloor$ for positive integers $n$. Fix $a$. $p$ is prime means $a$ do not divide $p$, so $ma > p > (m-1)a$ assumption valid for some $m$. Thus $m + R(ma) > a$. But $ma > p$ so $R(ma) \ge ma - p$, or $m + ma - p > a$. Thus $a > \frac{p-m}{m-1} = \frac{p-1}{m-1} - 1$. But $a < \frac{p}{m-1}$ so $a \le \frac{p-1}{m-1}$ by the Integer Bounding Argument 1 (IBA 1). Hence these two inequalities and IBA 2 gives $a = \lfloor \frac{p-1}{m-1} \rfloor$. Now we prove $a = \lfloor \frac{p-1}{n} \rfloor$ works. But this too easy. Thought process spoiler: p = s (mod k), s < k: $m + R(m (p-s)/k) > (p-s)/k$ $m = kt + q: 1 \le q \le k$ $kt + q + R(t(p-s) + q(p-s)/k) > (p-s)/k$ $kt + q + R(-st + q(p-s)/k) > (p-s)/k$ $kt + q - st + q(p-s)/k > (p-s)/k$ Clearly true. Now reverse our steps. Note that $R(-st + q(p-s)/k) \ge -st + q(p-s)/k$ because $-st + q(p-s)/k \le q(p-s)/k < p-s < p$.
06.02.2019 18:44
Might be similar with the other solutions: For $1\le a,m \le p-1$, say that $a$ has the $m$-property if and only if $m+R(ma)>a$. Let $u=\left\lfloor \frac{p-1}{a} \right\rfloor (\ge 2)$. Claim 1. If $a$ has the $u$-property, then $a$ is one of the forms $\left\lfloor \frac{p-1}{k} \right\rfloor$, where $k$ runs through $1,2, \cdots, p-1$. Note that $u$ is the minimal integer with $ua>p$. Hence $(u-1)a<p<ua$, and $p<ua<2p$, and $$u+R(ua)=u+ua-p>a \iff a>\frac{p-u}{u-1}.$$First assume that $a$ is on the form $\left\lfloor \frac{p-1}{k} \right\rfloor$. Then $u=k+1$, so $$a>\frac{p-1}{k}-1=\frac{p-1}{u-1}-1=\frac{p-u}{u-1}.$$Now assume that $a$ has the $u$-property, then $\frac{p-u}{u-1}<a<\frac{p}{u-1}$, or $\frac{p-u}{u-1}<a\le \frac{p-1}{u-1}$; thus $a=\left\lfloor \frac{p-1}{u-1} \right\rfloor$. Claim 2. If $a$ has the $u$-property, then $a$ has the $m$-property for all $1 \le m \le p-1$. For each $k=1,2, \cdots, a-1$, denote the minimal integer $t$ with the property $ta>kp$ by $u_k$. It is sufficient to check that $a$ has the $u_k$-property for each $k=1,2, \cdots , a-1$. Note that $(u-1)a<p<ua$, and $(u_k-1)a<p<u_ka$ gives $k(u-1)<u_k<ku$, or $u_k=ku-j_k$, where $1\le j_k \le k-1$. Hence $$u_k+R(u_ka)=u_k+u_ka-kp=ku-j_k+kua-aj_k-kp=k(u+ua-p)-(a+1)j_k\ge k(a+1)-(a+1)j_k \ge a+1>a$$, so $a$ has the $u_k$-property. Hence, the solutions are : $a = \left\lfloor \frac{p-1}{n} \right\rfloor$, for each $n=1,2, \cdots, p-1$.
06.02.2021 23:22
The answer is $\lfloor \frac{p-1}{n} \rfloor.$ Fix $n$. Consider all $a$ such that $(n-1)a<p<na.$ Suppose there is more than one $a$. Note the set of such $a$'s form a continuous interval, call $[x,y]$. I claim only $y$ works. First I show others don't work. Suppose consider $y-k\ge x,$ where $k>0.$ Then note $$n+R(n(y-k))=n+n(y-k)-p> y-k$$ $\leftrightarrow (n-1)+(n-1)(y-k)\ge p$ So $(n-1)(y-k+1)\ge p,$ which is a contradiction because $(n-1)y<p<ny.$ It remains to show that $y$ works. Notice this $y$ also satisfies $p<(n-1)(y+1)$ Claim: $R((a-n+1)y)-R(ay)<n-1.$ Proof. Assume $R(ay)<R((a-n+1)y)$. Note $(n-1)y<p$, so $R((a-n+1)y)-R(ay)=p-(n-1)y$. Since $(n-1)(y+1)>p,$ it follows that $p-(n-1)y-(n-1)<0,$ as desired. Therefore, $(a-n+1)+R((a-n+1)y) < a+R(ay),$ so we only need to check $1+R(y), 2+R(2y), \cdots, n-1+R((n-1)y)$. Since $(n-1)y<p, x+R(xy)=x+xy>y$ for all $1\le x\le n-1$, as desired. Notice this $y$ is just $\lfloor \frac{p-1}{n-1} \rfloor$, so the answer is $\lfloor \frac{p-1}{n} \rfloor.$
11.09.2023 00:50
For a postive integer $a$ let $f(a)$ denote the least number of the form $\frac{p}{k}$ such that $f(a) \geq a$. Then the answer is all $a$ such that $f(a)-a \leq 1$. This is equivalent to being of the form $\left\lfloor \frac{p-1}{k}\right\rfloor$—something I did not realize until reading this thread. However I think the first description is actually easier to work with anyways so ha. Fix $a$; write $f(a)=\frac{p}{k}$, then $a=\frac{p}{k}-q$. Then if $q>1$, by taking $m=k+1$ we have $$(k+1)+R((k+1)a)=(k+1)+R\left(p-kq+\frac{p}{k}-q\right)=(k+1)-kq+\frac{p}{k}-q<a+1,$$since $(k+1)a>p$ due to the definition of $a$. Hence only the advertised $a$ work. Now suppose $q \leq 1$. In general, we only have to consider $m<a$. Furthermore, if we wish to show that there are no $m<a$ such that $m+R(ma) \leq a$, then it suffices to show that no such $m$ exist such that $\left\lfloor \frac{ma}{p}\right\rfloor>\left\lfloor \frac{(m-1)a}{p}\right\rfloor$ (i.e. $ma$ is larger than some multiple of $p$ that $(m-1)a$ isn't). We have the following claim. Claim: These $m$ are precisely those of the form $ki+1$ (where $ki+1<a$). Proof: Observe that $$kia=pi-qki \text{ and } \frac{p}{k}-q=a\geq qa>qki,$$hence $kia<pi$ and $(ki+1)a>pi$ for all such $i$. $\blacksquare$ Then by our previous claim, we only have to check that $$(ki+1)+R((ki+1)a)=(ki+1)+R\left(pi-qki+a\right)=ki+1-qki+a>a \iff ki+1>qki,$$which is clear. $\blacksquare$
16.11.2024 02:21
The answer is all $a$ such that, when $p$ is divided by $a$, the quotient is at least the remainder. In other words, let $p=ra+s$ with $0\leq s\leq a-1$, then $a$ works if and only if $r\geq s$ (*) To show this is necessary, plug in $m=r+1$. Then, $R(a(r+1))=ar+a-(ra+s)=a-s$, so $$r+1+R(a(r+1))\geq a+1$$$$r+1+a-s\geq a+1$$$$r\geq s.$$ Now, we show that all such $a$ work. We say that $m$ just overflowed if there is a multiple of $p$ between $(m-1)a$ and $ma$. Clearly, it suffices to show that any $m$ that just overflowed works (as the other ones will have a strictly higher LHS). Because $p=ra+s\geq ra$, the gap between any two numbers that just overflowed is at least $r$. Thus, if we go from one just overflowed number to the next, the LHS will increase by at least $r+ra-ra-s$ (an increase of at least $r+ra$ from $m$ increasing by $r$, and a loss of $ra+s$ from the overflow). In particular, $r\geq s$, so this is nonnegative. Since the first number that just overflowed, $r+1$, has a LHS of at least $a+1$, all subsequent ones also do. We are done. (*) One can think of this as the top number in each "quotient bracket" with the exception of $r=1$, as if we stay in the same quotient bracket (value of $r$), increasing $a$ by $1$ will decrease $s$ by $r$, so there is exactly one point at which $s\leq r$ unless it ever reaches $s=r$ but that can only happen for $r=1$ because $p$ is prime. This is why this is equivalent to $a=\lfloor \frac{p-1}{r}\rfloor$, as this describes the top number in $r$'s quotient bracket, if it exists at all.