Un Calcul al CMMDC

 Problema Proprie

        Sa se determine $gcd(3\cdot n+1\;,\;5\cdot n+7)$.

SOLUTIE CiP

RASPUNS CiP  $(3\cdot n+1,5\cdot n+7)=\begin{cases}1,\;\;if\;n=2\cdot k \\2,\;if\;\;n=4\cdot k+3\\4,\;\;if\;n=8\cdot k+1\\8,\;\;if\;n=16\cdot k+13\\16,\;if\;n=16\cdot k+5\end{cases}$

REZOLVARE CiP

     Pe baza proprietatilor gcd

$(a,b)=(a+b\cdot m,b)=(a,b+a \cdot m)$ , for any integers $m$;

avem succesiv

 $(3n+1,5n+7)=(3n+1,5n+7-(3n+1))=(3n+1,2n+6)=(3n+1-(2n-6),2n+6)=$

$=(n-5,2n+6)=(n-5,2n+6-2(n-5))=$

$= (n-5,16)=\begin{cases}16,\;if\;n-5=16\cdot k\\8\;if\;n-5=16\cdot k+8\\4,\;if\;n-5 =16\cdot k+4\;or\;n-5=16\cdot k+12\\2\;if\;n-5=16\cdot k+\;2\;or\;6\;or\;10\;or\;14\\1\;if\;n-5=16\cdot k+\;1\;or\;3\;or\;5\;or\;7\;or\;9\;or\;11\;or\;13\;or\;15\end{cases}$

Obtinem imediat raspunsul.

$\blacksquare$

Rata Infectãri pe Judete si Localitãti

Vezi https://profesorjitaruionel.com/wp-content/uploads/2020/09/Analiza-epidemiologica-pe-judete-pentru-inceperea-anului-scolar-scenariu-rosu-galben-sau-verde.pdf

C H E S T I O N A R

 NONU Nicolae Laurentiu

CIOCIU Ilie Eduard

DRAGOI Darius

BAN Andreea Maria

DODOC Eugenia Alexandra

GAURUS Elena Denisa

CONSTANTIN Elena-Andra

CIOCIU AnaMaria

CIOCIU Tatiana

STELEA Sebastian

dinel zoltan

JIGA Elena Diana

PASU Iliuta

DRAGOI Leonard

JIGA Loredana Sorina

FURDUI Andreea

Problem MA 82 CRUX MATHEMATICORUM vol 46, no 7 pag 285

 

                    ANSWER CP : $\underset{\;\;n}max\;d_{n}=197$

 More precisely    $d_{197\cdot k -100}=197$ , $d_{n}=1\;\;if\;n\neq 197\cdot k-100$

Solution CP

      We apply the following properties:

(A)       $(a,b)=(a,-b)$;

(B)        $(a,b)=(a+b\cdot m,b)=(a,b+a \cdot m)$ , for any integers $m$;

(C)        if $(c,b)=1$ then $(a,b)=(a \cdot c,b)$.

Here $(a,b)$ denote "greatest common divisor" for integers $a$ and $b$. See for (C) an ancient post.

      Let $d_{n}=(a_{n},a_{n+1})=(n^{2}+2\cdot n+50, (n+1)^{2}+2(n+1)+50)=$

        $=(n^{2}+2\cdot n+50,n^{2}+4\cdot n+53)=$

        $\overset{(B)}=(n^{2}+2\cdot n+50,n^{2}-4\cdot n+53-(n^{2}+2\cdot n+50))=$

     $=(n^{2}+2\cdot n+50,2\cdot n+3)\;\overset{(C)}{=}\underset{(2,2n+3)=1}{=}{=}(2(n^{2}+2n+50),2n+3)=$

     $=((2n+3)n+n+100,2n+3)\overset{(B)}{=}(n+100,2n+3)\overset{(B)}{=}(n+100,2n+3-2(n+100))=$

     $\overset{(A)}{=}(n+100,197)$.

The number 197 being prime

             if $n+100=197\cdot k$ then $d_{n}=197$

             and if $n+100=197\cdot k+r$, $r=1, 2, ... ,196$ then $d_{n}=1$.

$\blacksquare$

          Examples

     $a_{96}=5458=2\cdot 4729;$

      $a_{97}=9653=7^{2}\cdot 197$,    hence $d_{96}=1$

      $a_{98}=9850=2\cdot 5^{2}\cdot 197 $,    hence $d_{97}=197$

      $a_{99}=10\; 049=13 \cdot 773$,     hence $d_{98}=1$

....................................................................................................

      $a_{293}=86\;485=5\cdot 7^{2}\cdot 353$

      $a_{294}=87\;074=2\cdot 13\cdot17\cdot 197$,     hence $d_{293}=1$

      $a_{295}=87\;665=5\cdot 89\cdot 197$,      hence $d_{294}=197$

      $a_{296}=88\;258=2\cdot 44\;129$,       hence $d_{295}=1$

A property of GCD (Greatest Common Divisor)

      We will denote the greatest common divisor of two integers $a$ and $b$ as $gcd(a,b)$. Some authors use $(a,b)$. A definition of $gcd(a,b)$, more generally valid in unitary commutative rings is

 

$d=gcd(a,b) \Leftrightarrow \begin{cases}d\;\mbox{divides}\;a\;\;and \;\;d\;\mbox{divides}\;b&(i)\\if\;d_{1}\;\mbox{divides} \;a\;and\;d_{1}\;\mbox{divides}\;b\;\;then\;\;d_{1}\;\mbox{divides}\;d&(ii)\end{cases}$ 

        Words $\underline{divides}$ means, in expresions "$d\;divides \;a$" etc, that

"there are an element $x$ in ring $\mathbb{Z}$ such that $d\cdot x=a$" etc.

We will denote "$d\;divides \;a$" by $d\mid a$.

 

     LEMMA If $gcd(c,b)=1$ then $gcd(a,b)=gcd(a\cdot c,b)$

 

Proof. Let $d=gcd(a,b)$; we have $d\mid a$ so $d \mid a\cdot c$. Thus, first

$d \mid a\cdot c$  and   $d \mid b  $  (i')

Secondly, let $\delta$ be such that

(1)                           $\delta \mid a\cdot c$  and  $\delta \mid b$.

$gcd(c,b)=1\Rightarrow$ there are integers $u$ and $v$ such that

(2)                                 $c\cdot u+b \cdot v =1$.

From $\delta \mid b \Rightarrow \delta \mid b\cdot v$  $\overset{(2)}{\Rightarrow} \delta \mid 1-c \cdot u \Rightarrow \delta \mid a-a\cdot c \cdot u \overset{(1)}{\Rightarrow} \delta \mid a$.

     Thus, (1) $\Rightarrow \delta \mid a$ and $\delta \mid b$ so that , via (ii) from definition,

$\delta \mid d$. Finally

$(1) \Rightarrow \delta \mid d$  (ii')

that means - from (i') and (ii"), $d=gcd(a,b)$.

 

 

$\blacksquare$

Remark. Here are another discussion about such phaenomena.

 

 

    

Problem MA78 - Crux Mathematicorum Vol. 46, No. 6 , June, 2020

 

 

 ANSWER CiP : $n=667$

 Verification: $T(667)+3 \cdot 667=6+6+7+3\cdot 667=19+2001=2020$

SOLUTION CiP

Let $n=\overline{abc}$, $a\neq 0$; the given equation is written

$$a+b+c+3\cdot (100a+10b+c)=2020$$

$$\Leftrightarrow a+b+c+30(10a+b)+3c=2020$$

where do we get

(1)$$30\cdot \overline{ab}=2020-a-b-4c.$$

From equation (1) we see that $30\mid2020-a-b-4c$ and because $a, b, c$  are digits in base ten, we have $a+b+4c\geq 9+9+36=54$. Then the right member of (1) is $\geq 1966$ so its values can only be 2010 or 1980. Also from 1 we get

(2)$$\overline{ab}=\frac{2020-a-b-4c}{30} .$$

If $a+b+4c=10$ then $\overline{ab}=\frac{2010}{30}=67$ but $a=6,b=7$ they cannot check the condition $a+b+4c=10$.

If $a+b+4c=40$ then $\overline{ab}=\frac{1980}{30}=66$ so $a=6,b=6$ and $c=\frac{40-6-6}{4}=7$ which is the answer.

$\blacksquare$

 ===============

Added February 8, 2021

             Good answer  see V47n01, page 8-9

              They write in their solution that $T(n)=2020-3n$ and since for a three-digit number $n$

$1 \leq T(n) \leq27$

$\Leftrightarrow \; 1 \leq 2020-3n \leq27$

.......$\Leftrightarrow \;\;665 \leq n \leq 673$.

           On the other hand $n \equiv T(n) \;(mod\;3)$ and $T(n)+3n=2020 \; \Rightarrow$

$\Rightarrow \;T(n) \equiv 2020\;(mod\;3)$ $\Rightarrow \;T(n) \equiv 1\;(mod\;3)\;\;\Rightarrow \;n \equiv 1 \; (mod\;3)\;....\;\Rightarrow \;3 \mid (n-1)$.

          From the above two observations, we know that, if such $n$ is possible then it must be either $667,\;670$ or $673$, and we check each possibility ....

= end added=

 

 

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.$