Let $k$ be fixed positive integer . Let $Fk(n)$ be smallest positive integer bigger than $kn$ such that $Fk(n)*n$ is a perfect square . Prove that if $Fk(n)=Fk(m)$ than $m=n$.
Problem
Source: Serbia national Olympiad Day 1 problem 2
Tags: number theory, TST
28.03.2015 13:25
My solution: If we represent $n=p1^(a1)*p2^(a2)*.....*pk^(ak)$( $pf$ powered by $af$) where $pj$ is prime, let for every$aj$ that is odd $pj|N(n)$ and if $pj|N(n)$ $\implies N(n)\equiv x(mod pj^2)$ where $x$ is nonzero integer. Basically $N(n)$ is non square part of $n$. Now let $Q(n)$ be square part of $n$, so for every $pj^(aj)||Q(n)$ $\implies aj$ is even, and it holds $Q(n)*N(n)=n$ for every $n$ from set of positive integers. Trivial case is $k=1$ . Assume $k>1$ Let$ K(x)$ where $x$ is positive integer be first perfect square bigger than $x$. Lemma 1 : For every positve integer there is uniqe representation as $Q(n)*N(n)=n$. Proof 1:: Because we can represent every integer by its prime factors like $n=p1^a1*p2^a2*.....*pk^ak$ it is trivial that it is unique partition of set of $pi$ on ones with even and ones with odd exponent. Lemma 2 : If $k$ is a positive integer bigger tha $1$ than for every $a$ positive integer between $ka^2$ and $k(a+1)^2$ exists a perfect square. Proof 2: It is sufficent to show that there exist integer beetwen $\sqrt(k)*a$ and $\sqrt(k)*(a+1) $ which is trivial because $\sqrt(k)>1$. Lemma 3 : If $ K(kx^2)=K(ky^2)$ for positive integers $k,x,y$ than $x=y$. Proof 3 ; Directly from Lemma 2. Let $n=Q(n)*N(n)$ and $m=Q(m)*N(m)$ . Because $Fk(n)*n=Fk(n)*Q(n)*N(n)$ is perfect square and $Q(n)$ is a perfect square so must $ Fk(n)*N(n)$. Now because $N(n) $ is not a perfect square than $Fk(n)=y*N(n)$for some $y$ where $y$ is a perfect square . So now we have $y*N(n)>k*n=k*Q(n)*N(n)$ now $y>Q(n)*k$ so $y=K(k*Q(n))$. So we get $Fk(n)=K(kQ(n))*N(n)$ Similary for $m$ . Now from $Fk(n)=Fk(m)$ we get $K(kQ(n))*N(n)=K(kQ(m))*N(m)$ , now by Lemma1 it must be $N(n)=N(m)$. Now we have $K(kQ(n))=K(kQ(m))$ now by Lemma 3 we have $Q(n)=Q(m)$ which now $\implies m=n$. So we are done.
24.12.2017 16:17
its more obvious than that. assume T=least perfect square bigger than k . so f(n).n=G^2 >= k.n^2 thus G>=r.n (r^2=T and f(n) is Fk(n) ) . and since f(n) is the least number satisfying then G=r.n (why?) so f(n)=T.n . and the rest is obvious.
06.02.2020 17:07
Let s(n) be the smallest number for wich n*s(n) is a perfect square. Now notice that n and Fk(n) are both divisible by s(n), so it means that we can write Fk(n) as kn+a*s(n) and Fk(m) as km+b*s(m) where a and b are some positive intergers. Also, notice that numbers n/s(n) and Fk(n)/s(n) are both perfect squares. So let Fk(n) =s(n)*x^2, Fk(m)=s(n)*y^2, n=s(n)*i^2 and m=s(n)*j^2. Now since Fk(n)=Fk(m) we have s(n)*x^2=s(m)*y^2 i. e. s(n)/s(m)=(y/x)^2. Now if s(n)/s(m)=p/q where p and q are co-prime numbers we have that p and q are perfect squares, but since each prime number in factorization of numbers s(n) and s(m) is of degree 1(for example if p1^a1*p2^a2*...pl^al is a factorization of number s(n), then a1=a2=...=al=1) we have that p=q=1 i. e. s(n)=s(m). Now, let's get back to our original equality kn+a*s(n)=km+b*s(m). Since s(n)=s(m) we have x^2=k*i^2+a=k*j^2+b. We have k*i^2, k*j^2 € [(x-1)^2, x^2) i. e. k^(1/2)*i, k^(1/2)*j € [x-1, x) . From here we have that |k^(1/2)*i-k^(1/2)*j| < x-(x-1)=1 i. e. k^(1/2)*|i-j|<1. Since k^(1/2)>=1 we have that i-j= 0 i.e. i=j i.e n=m
06.02.2020 17:17
06.02.2020 17:27
Are you talking about my solution?
06.02.2020 17:41
IvanMitrovic wrote: Are you talking about my solution? No I was talking about the problem and my solution.
06.02.2020 23:32
stroller wrote: If I'm not mistaken this is quite troll Suppose $F_k(n) = F_k(m)$. Then $F_k(n)nF_k(m)m$ is a perfect square, hence $nm$ is a perfect square. WLOG $n < m$. Then $F_k(m) > km \ge m \ge F_k(n)$, contradiction. Why does it holds Fk(n)=<m?
07.02.2020 04:33
IvanMitrovic wrote: stroller wrote: If I'm not mistaken this is quite troll Suppose $F_k(n) = F_k(m)$. Then $F_k(n)nF_k(m)m$ is a perfect square, hence $nm$ is a perfect square. WLOG $n < m$. Then $F_k(m) > km \ge m \ge F_k(n)$, contradiction. Why does it holds Fk(n)=<m? It doesn't. Whoops my "solution" only holds when $k = 1$... thanks for pointing out
06.10.2023 20:29
06.10.2023 21:28
Let $n=a^2x$ and $m=b^2x$ where $x$ is squarefree. Then, $F_k(n)=x\left\lfloor\sqrt{\frac{kn}x}+1\right\rfloor^2=x\left\lfloor a\sqrt k+1\right\rfloor^2$ and $F_k(m)=x\left\lfloor b\sqrt k+1\right\rfloor^2$, so we must have $a=b$, implying $m=n$.