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 $r_{i,j}$ for the remainder of $i \times j \div p$.
Now for an integer $u \in \{1, 2, \dots, p-2\}$, 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' \in \{1, 2, \dots, p-2\}$, we can define $K_\nu'$ for $\nu=1,2,3,4$.




Question.
If $K_1 =K_1'$ and $K_4=K_4'$, then either $K_2=K_2'$ and $K_3=K_3'$, or $K_2=K_3'$ and $K_3=K_2'$.



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 $K_1 =K_1'$ and $K_4=K_4'$, 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...