joi, 9 aprilie 2020

SIMULTANEOUS DIVISIBILITY of 1-FORMS

          Is about Problem 1 from Eőtvős Mathematical Competition 1894.
In Romanian there is this book: "Probleme de matematica pentru concurs";
the book can be downloaded from here (the solution is on the pages 23-28).

          The stattement of the problem can be written as a logical equivalence

$(1)$                                      $17 \; \mid 2x+3y \; \; \Leftrightarrow \; 17 \; \mid 9x+5y.$

          We will give a list of equivalences, "completely" in some sense, from which we can deduce (almost) any of such a relations. 

LEMA For any integers $x$, $y$ the following equivalences hold:

$17 \; \mid \; I(x,y)=2x+3y \; \Leftrightarrow \; 17 \; \mid \;II(x,y)=x-7x \; \Leftrightarrow \; 17 \; \mid \; III(x,y)=3x-4y \; \Leftrightarrow $

$\Leftrightarrow \;17 \; \mid \; IV(x,y)=5x-y \; \Leftarrow \; 17 \; \mid V(x,y)=7x+2y \; \Leftarrow \; 17 \; \mid \; VI(x,y)=8x-5y.$


Proof. We have $17 \; \mid 2x+3y \; \Leftrightarrow \; \widehat{2}x+\widehat{3}y=\widehat{0}$, where $\widehat{m}$ mean the congruence class modulo $17$ determined by $m$; their set is $\mathbb{Z}/17\mathbb{Z}$ (actually it is the field $GF(17)$). If we multiply last equation by $\widehat{9}$ and we take into account that, in $GF(17)$,
 $\widehat{9} \cdot \widehat{2}=\widehat{1}, \; \widehat{9} \cdot \widehat{3}=\widehat{10}=-\widehat{7}$
we obtain $\widehat{1}x-\widehat{7}y=\widehat{0} \; \Leftrightarrow \; 17 \; \mid \; x-7y$.
          In the same way, starting with $\widehat{2}x+\widehat{3}y=\widehat{0}$ and multiplyng it by $\widehat{10}$, $\widehat{11}$, $\widehat{12}$, $\widehat{4}$ respectively, we get the remained equivalences.
$\blacksquare$

          Apparently we didn't find the desired result. It comes if we were to multiply $\widehat{2}x+\widehat{3y}=\widehat{0}$ by $\widehat{13}$ and taking into account that
 $\widehat{13} \cdot \widehat{2}=\widehat{9}$ and $\widehat{13} \cdot \widehat{3}=\widehat{5}$ 
but patience $\cdot$ $\cdot$ $\cdot$ The word "completely" means that no other divisibility relation that can be obtained from $17 \mid 2x+3y$ it must be able to be expressed by ones of the forms $I-VI$ (and apliying other simple divisibility properties). From example
$$17 \; \mid I(x,y) \; \stackrel{LEMA} \Leftrightarrow  17 \; \mid VI(x,y) \Leftrightarrow 17 \; \mid 17x-VI(x,y)=9x+5y.$$

          Finally, we conclude anothers equivalences that we will use in a similar problem:


$7\; \mid x+2y \; \Leftrightarrow \; 7 \; \mid 2x-3y \; \Leftrightarrow \; 7 \; \mid 3x-y;$


$7\; \mid 3x+y \; \Leftrightarrow \; 7\; \mid x-2y \; \Leftrightarrow \; 7 \; \mid 2x+3y.$

2 comentarii:

  1. Hi, mist
    "Finally"" in your last three rows contain redundant affirmations (I.e. more than necessary)
    Is enoug to change "y" in first row of equivalences with "-y" in order to obtain the second row of equivalences (or vice versa).
    Oh, dear, if we multiply x+2y with ^2 , ^3 respectively, we obtain all of 1-forms needed for a "completely" list of congruences.

    RăspundețiȘtergere
  2. I am not very expert, but I would like to collaborate, would you let me? I am from Latin America.

    RăspundețiȘtergere