Do we conclude from these relations that $ny-hx \mid x(nx-h)$?

245 Views Asked by At

We have the following relations $$p^i \mid ny-hx \\ (ny-hx)q=(nx-h)n^f \\ p^i \mid x(nx-h)$$ where $p$ is a prime, $x, y \in \mathbb{Z}$, $n>1$, $|h|<n$, $hx\geq 0$, $i>0$.

Do we conclude from these relations the following? $$ny-hx \mid x(nx-h)$$

$$$$

EDIT:

I am looking at the following proof:

enter image description here enter image description here enter image description here

$$$$

At the part "By the Chinese Remainder Theorem ... $ny-hx \mid x(nx-h)$."

I haven't understood how from the relations $(7)$ and $(5)$ we conclude that $ny-hx \mid x(nx-h)$.

Could you explain it to me?

1

There are 1 best solutions below

11
On BEST ANSWER

First of all, the part of the proof you don't understand is (correct me if I'm wrong).

  1. We can prove easily that, by the Chinese remainder theorem there exists an $h\mod n$ such that $h=h(p) \mod p$ for every prime $p$ dividing $n$. (this one is clear ?)
  2. $(7)$ For every prime $p$, if $h=h(p) \mod p$ then $$ p^i| ny-hx \implies p^i|x$$
  3. $(5)$ For all $k$ such that $|k|<n$ we have : $$ny-kx|_n nx-k $$

Question : How can we deduce from $1.,2.$ and $3.$ that $ny-hx|x(nx-h)$ ?

1. Sketch or hint As we can see, from $1.$ we can apply $2.$ for every prime $p$ which divides $n$ hence we would say that "the commune part between $n$ and $ny-hx$ must divide $x$" and from $3$ we can deduce that "the other part of $ny-hx$ must divide $nx-h$". These two observations both implies that $ny-hx$ divides $x(nx-h)$

2. Solution : In order to justify $1$, let $n=q_1^{\alpha_1}\cdots q_k^{\alpha_k}$ the factorization of $n$. let $a_i=0$ if $ny$ and $x$ are divisible by the same powers of $q_i$ and $a_i=1$ otherwise, this means that $a_i=h(q_i)$ for every $i=1,\dots,k$. the Chinese remainder theorem implies that there exist an $h<n$ such that: $$\begin{align}h&\equiv a_1\mod q_1\\ h &\equiv a_2 \mod q_2 \\ h &\equiv \cdots \mod \cdots \\h &\equiv a_k\mod q_k\end{align} $$.

Now we can write : $$ny-hx =q_1^{r_1}\cdots q_k^{r_k} a \quad \gcd(a,n)=1\tag {*}$$ for every $i=1,cdot,k$ we have $h=h(p_i)\mod p_i$ so we can apply $2$: because $q_i^{r_i}$ divides $ny-hx$ hence $q_i^{r_i}$ divides $x$ this is true for every $i=1,cdot,k$ then : $$q_1^{r_1}\cdots q_k^{r_k}|x \tag{**}$$

But we have also $h<n$ so we can apply $3.$ hence there exists $f,q$ such that $$(ny-hx)q=(nx-h)n^f $$ but $a|ny-hx$ hence $a|(nx-h)n^f$ and because $\gcd(a,n^f)=1$ we can deduce (using Euclid's lemma) that $a|nx-h \tag {***}$ Finally from ($*$),($**$) and ($***$) we can deduce the result.

Observation : In the beginning you wrote the problem without quantifiers and conditions which gives another sense to the assertions so every time you copy a problem you have to understand the relevant parts of implications and the result you may for example write:

Let $h,n,x,y$ be some integers such that : $$\begin{align}\exists f,q \quad (ny-hx)q=(nx-h)n^f \\ \forall i>0 \quad p^i| ny-hx \implies p^i|x\end{align}$$ for every prime $p$ dividing $n$ (which is equivalent to $h=h(p)\mod p$ because of the definition of $h$)

If you have written the problem this way there would not be such a misunderstanding.