Let $a$, $b$ and $n$ be positive integers, satisfying that $bn$ divides $an-a+1$. Let $\alpha=a/b$. Prove that, when the numbers $\lfloor\alpha\rfloor,\lfloor2\alpha\rfloor,\dots,\lfloor(n-1)\alpha\rfloor$ are divided by $n$, the residues are $1,2,\dots,n-1$, in some order.
Problem
Source: Spain MO 2024 P6
Tags: number theory, Spain
16.03.2024 18:53
Ignore...
16.03.2024 20:24
PRMOisTheHardestExam wrote: a=31 b=14 n=10 not working Why do you think so? The numbers are $2,4,6,8,11,13,15,17,19$ which gives exactly the nine residues $2,4,6,8,1,3,5,7,9$ modulo $10$...
17.03.2024 04:20
Sorry I made calculation error Any solution???
17.03.2024 05:08
17.03.2024 05:34
Quidditch wrote: Let $$ak\equiv t\pmod{b}\implies nb\mid ak-t$$where $0\leq t<b$. How do u get this? $n,b$ cannot be sure relatively prime.
17.03.2024 05:42
@above because I assumed that $\lfloor\alpha k\rfloor\equiv 0\pmod{n}$ and $\lfloor\alpha k\rfloor$ is actually exactly $\frac{ak-t}{b}$.
26.11.2024 00:10
Let \[k=\frac{an-a+1}{bn}.\]Let $x_m=\lfloor m\alpha\rfloor$. Then \[x_{n-1}=\left\lfloor\frac{an-a}{b}\right\rfloor=\frac{an-a+1}{b}-1\equiv -1\pmod n.\]Consider the transformation by adding $\frac{1}{n-1}$ to $a$. The idea is that this is not going to affect anything until $x_{n-1}$, when it boosts $x_{n-1}$ to $0$ mod $n$. Thus we want to prove that $x_1,x_2,\dots,x_{n-2}$ is $1,2,\dots,n-2$ in some order. But now note that \[m\cdot\frac{a+\frac{1}{n-1}}{b}=m\cdot\frac{a(n-1)+1}{b(n-1)}=\frac{(km)n}{n-1}.\]But note that for any integer $c$, we have \[\left\lfloor\frac{cn}{n-1}\right\rfloor\%n=c\%(n-1).\]But now it is obvious why $km$ spans every nonzero residue mod $n-1$ exactly once: it's from $\gcd(k,n-1)=1$ because $k\mid a(n-1)+1$. $\blacksquare$