Saturday, December 16, 2017

elementary number theory - A question on the remainders of integer division

This is a question on the remainders of integer division from my student.



Notations.

Let p be a positive odd prime integer.
We write ri,j for the remainder of i×j÷p.
Now for an integer u{1,2,,p2}, we define
\begin{align*}
K_1 =&\{ i : 1 \le i \le p-2,\ r_{i,u}+uK_2 =&\{ i : 1 \le i \le p-2,\ r_{i,u}+uu+1\}, \\
K_3 =&\{ i : 1 \le i \le p-2,\ r_{i,u}+u>p,\ r_{i,p-u-1} K_4 =&\{ i : 1 \le i \le p-2,\ r_{i,u}+u>p,\ r_{i,p-u-1} >u+1\}.
\end{align*}
And for another u{1,2,,p2}, we can define Kν for ν=1,2,3,4.




Question.
If K1=K1 and K4=K4, then either K2=K2 and K3=K3, or K2=K3 and K3=K2.



What I have done.



1.
With the help of computer, I checked the correctness of this question for p<100.



2.

Still with the help of computer, I found that, at least for p<100, if K1=K1 and K4=K4, then either u \equiv u' \pmod{p} or u+u' \equiv p-1 \pmod{p}.
The first case corresponds to the result K_2=K_2' and K_3=K_3', and the second one corresponds to the result K_2=K_3' and K_3=K_2'.



3.
I observed the definitions of the K_\nu's, and found some equivalent conditions.
Firstly, we have
\begin{align*}
r_{i,u}+u

r_{i,u}+u>p &\quad\Leftrightarrow\quad r_{i+1,u} =r_{i,u} +u-p,
\end{align*}

and similarly,
\begin{align*}
r_{i,p-u-1} r_{i,p-u-1} >u+1 &\quad\Leftrightarrow\quad r_{i+1,p-u-1} =r_{i,p-u-1} +(p-u-1) -p.
\end{align*}



4.
Using the discussion in (3), we obtain
\begin{align*}
i \in K_1

&\;\Leftrightarrow\; r_{i,u}+r_{i,p-u-1}

p, \\
i \in K_4
&\;\Leftrightarrow\; r_{i,u}+r_{i,p-u-1}>p \text{ but } r_{i+1,u}+r_{i+1,p-u-1}i \in K_2 \cup K_3
&\;\Leftrightarrow\; \text{both r_{i,u}+r_{i,p-u-1} and r_{i+1,u}+r_{i+1,p-u-1} are $p$}.
\end{align*}



5.
Now by the result in (4), we can see that K_1 =K_1' and K_4=K_4' if and only if for every i \in \{1, 2, \dots, p-1\}, the signatures of r_{i,u}+r_{i,p-u-1}-p and r_{i,u'}+r_{i,p-u'-1}-p are the same (i.e., both positive or both negative).




However, I really do not know how to solve this question, so if you have any idea, please help me.
Thank you very much for your attention.






Any ideas or hints are welcome. Please.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...