0
$\begingroup$

To find the number of non-negative integer solutions of $$[x/m]=[x/n], \quad m,n \in \mathbb{N}, m>n, \text{gcd}(m,n)=1 ~~~~(*)$$ where $[.]$ denotes Greatest Integer Function (GIF).

By the estimation of $[F]$ as: $F-1 <[F]\le F$, we get

$$x/m-1<[x/m]\le x/m ~\text{and}~x/n-1<[x/n]\le x/n$$ Combining these two we get a good estimate for $x$ as $$-\frac{mn}{m-n}< x< \frac{mn}{m-n}$$ For the solutions of (*), we find that $n$ becomes the last term of an A.P with first term as $1$ and common difference as $(m-n)$. $$T_N=n=1+(N-1)(m-n) \implies N=\frac{m-1}{m-n}$$ then the number of non-negative integer solutions become the sum of this A.P of $N$ terms as $$S_N=\frac{N(n+1)}{2}. ~~~~~~(**)$$ We have verified this for several cases of $(m,n)$ pairs as $(3,2), (6,5), (11,9),....(101,99).$

The question:

Our result $(**)$ is restricted to the cases where $N$ is whole number? What could be its generalization? Any comment is welcome.

EDIT(Examples):

(i) The number of non-negative solutions of $[x/6]=[x/5]$ are 5+4+3+2+1=15.

(ii) The number of non-negative solutions of $[x/11]=[x/9]$ are 9+7+5+3+1=25.

(iii) The number of non-negative solutions of $[x/99]=[x/101]$ are 99+97+95+93+.....+3+1=2500.

(iv) The number of non-negative solutions of $[x/11]=[x/6]$ are 6+1=7

In the case of:

How many positive integer solutions exist for $[\frac{x}{19}]=[\frac{x}{20}]$, where $[x]$ denotes the Greatest integer function

we get $$N=(20-1)/(20-19)=19, S_N= \frac{19\cdot 20}{2}=190.$$

$\endgroup$
7
  • 1
    $\begingroup$ I mean, it is true for all $m,n$ when $0\neq x<1.$ How does that relate to your statement about the arithmetic progression? Can you elaborate on the claim starting with "We find..." It doesn't appear to be true when $n=4,m=2,$ $\endgroup$ Commented Jul 9 at 18:13
  • $\begingroup$ The core case is when $n=m+1.$ If it is true for any $n,m$ it is also true for $n',m'$ for any $m\leq m'\leq n'\leq n.$ $\endgroup$ Commented Jul 9 at 18:16
  • $\begingroup$ (Whoops, my last comment reversed which variable was greater.) $\endgroup$ Commented Jul 9 at 18:20
  • $\begingroup$ @Thomas Andrews We have discussed the cases where gcd(m, n) =1. $\endgroup$
    – Z Ahmed
    Commented 2 days ago
  • 1
    $\begingroup$ So, are you seeing that if $\gcd(m,n)=1$ then $n=1+(N-1)(m-n),$ for some $N?$ This isn't true. $n=5,m=11$ is a counterexample. $\endgroup$ Commented 2 days ago

1 Answer 1

0
$\begingroup$

Let $m,n\in\Bbb{N}$ with $\gcd(m,n)=1$ and $m>n\geq1$ be given. Let $x\in\Bbb{N}$ be such that $[x/m]=[x/n]$. Write $$x=q_mm+r_m\qquad\text{ and }\qquad x=q_nn+r_n,$$ for some nonnegative integers $q_m,r_m,q_n,r_n\in\Bbb{N}$ with $r_m<m$ and $r_n<n$. Then $$q_m=[x/m]=[x/n]=q_n,$$ and so for $q:=q_m=q_n$ we see that $$qm\leq qm+r_m=qn+r_n<qn+n=(q+1)n,$$ which shows that $q<\frac{n}{m-n}$. Now for each value of $q$, we want to count the number of solutions $(r_m,r_n)$ to $$qm+r_m=qn+r_n,$$ with the restrictions that $0\leq r_n<n$ and $0\leq r_m<m$. Of course this is equivalent to $$r_n=q(m-n)+r_m,$$ and recalling that $n<m$, we see that the number of solutions is precisely $n-q(m-n)$. It follows that the total number of solutions is $$\sum_{q=0}^{\tfrac{n}{m-n}-1}\left(n-q(m-n)\right)=\frac{n^2}{m-n}-(m-n)\sum_{q=0}^{\frac{n}{m-n}-1}q=\frac12\frac{n^2}{m-n}+\frac n2.$$ Note that this does not use the fact that $\gcd(m,n)=1$, only that $m>n\geq1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .