Surjectivité d'une fonction définie sur $\Z^2$ 23 mai 2024

etanche

Bonjour

Déterminer tous les $(a,b,c)\in \Z^3$ tels que $g(x,y)=cxy+by+ax$ soit surjective de $\Z^2$ dans $\Z$

Merci

Source AMM 12475

zygomathique

salut

pour faire avancer le schmilblick ...   

si $c = 0$ alors il suffit que a et b soient premiers entre eux puisqu'alors $g(kx, ky) = kby + kax = kg(x, y)$ et qu'il existe (u, v) tel que $g(u, v) = au + bv = 1$

gebrane

$nxy+mx+py=q \iff (nx+p)(ny+m)=(pm+nq)$

Titi le curieux

Bonjour, 

Je change les notations de gebrane pour coller avec l'énoncé d'etanche:

 $cxy + ax + by = z \Leftrightarrow (cx + b)(cy + a) = (ab + cz)$ où $z=g(x,y)$

  Cette assertion est vrai lorsque $c \neq 0$, vu que le cas $c=0$ est résolu, on s'y restreint pour la suite.

  En utilisant l'équivalence de gebrane on voit qu'il y a la condition suffisante  $a \equiv 1 \pmod c$ (ou $b \equiv 1 \pmod c$). Je ne sais pas si c'est nécessaire.

zygomathique

j'avais pensé à cette factorisation classique après avoir posté donc je n'ai pas voulu refaire un post ... mais de toute façon pour que g soit surjective il est évidemment nécessaire que pgcd (a, b, c) = 1

ta condition semble plus forte ...

gebrane

Laissons etanche terminer

etanche

Ce que j’ai écrit ci-dessous est faux, voir le post de depasse plus bas.
———————————
D’après zygomatique si pgcd(a,b,c)= alors il existe $(x,y,z) \in Z^3$ tel que $ax+by+cxy=1$

Ce qui donne la surjectivité de $g$.
———————————-

Titi le curieux

 Je vais désobéir à gebrane (désolé gebrane):

 Ma condition était trop forte en fait c'était  $a\equiv \pm 1 \pmod c$ ou $b \equiv \pm 1 \pmod c$.

 La condition est suffisante, mais je ne suis pas certain qu'elle soit nécessaire, sauf peut-être dans le cas où $c$ est premier avec $ab$ si on me dit que lorsque  $p$ et $q$ sont premiers entre eux alors il existe une infinité de nombre premiers de forme $p + nq$.

@etanche : là tu t'avances un peu, zygomathique a bien précisé que la condition est nécessaire, mais pas plus. L'idée c'est juste que si le pgcd est un entier $n$, alors l'image de $g$ est dans $n\mathbb{Z}$. Je ne sais même pas l'existence d'un triplet $(x,y,z)$ tel que $ax+ by+ cxy = 1$ (dont il ne parle pas)  implique la surjectivité de $g$, ce n'est pas comme si $xy$ était indépendant de $x$ et $y$.

depasse

Titi le curieux a dit :

 

Je ne sais même pas l'existence d'un triplet $(x,y,z)$ tel que $ax+ by+ cxy = 1$ (dont il ne parle pas)  implique la surjectivité de $g$, ce n'est pas comme si $xy$ était indépendant de $x$ et $y$.

Corrigé de coquilles:

Titi le curieux a dit :

 

Je ne sais même pas si l'existence de $(x,y)$ tel que $ax+ by+ cxy = 1$ (dont il ne parle pas)  implique la surjectivité de $g$, ce n'est pas comme si $xy$ était indépendant de $x$ et $y$.

Bonsoir,
je me suis permis de corriger deux coquilles (je crois) de Titi le curieux .
@Titi le curieux
L'existence de $(x,y)$ tel que $ax+ by+ cxy = 1$ n'implique pas la surjectivité de $g$:
En effet, l'exemple $(a,b,c)=(2,2,5)$ le montre:
Si $(x,y)=(-1,-1)$, on a bien $ax+ by+ cxy = 1$;
En revanche, $2x+2y+5xy=3$ est sans solution:
En effet,  $2x+2y+5xy=3$ équivaut à $(5x+2)(5y+2)=2*2+5*3=19$, premier;
or  $(5x+2)$ (ou $(5y+2)$!) ne sont jamais $1$ ou  $-1$.
Cordialement
Paul

etanche

Si $c\neq 0$ y a pas surjectivité.

jandri

Pour $c=1$ il est immédiat que $g$ est surjective.

J'ai montré que pour $2\leq c\leq 4$ et ${\rm pgcd}(a,b,c)=1$ l'application $g$ est également surjective.

En revanche comme la démontré @depasse l'application $g$ n'est pas surjective quand $c=5$ dans le cas où $a=b=2$.

Ben314159

Pour $c\!\not=\!0$, il y a au moins les cas triviaux où $a$ (ou $b$) est congru à $\pm1$ modulo $c$ qui marchent vu que, si $a\!+\!\lambda c\!=\!\pm 1$ avec $\lambda\!\in\!\Z$ alors $x\mapsto g(x,\lambda)\!=\!\pm x\!+\!\lambda b$ est clairement surjective.

gebrane

Amusement : Pour c=1, l'équation 4y + 5x = xy admet exactement 6 solutions dans $\N^2$

JLT

Pas le temps de me pencher sur le problème mais on peut montrer déjà que si $a$ et $b$ sont premiers avec $c$ et non congrus à $\pm 1$ modulo $c$ alors $f$ n'est pas surjective.

Ben314159

En utilisant la factorisation standard $g(x,y)=\frac{1}{c}\big((cx\!+\!b)(cy\!+\!a)-ab\big)$ (pour $c\!\not=\!0$ bien sûr) le problème revient à montrer que tout entier $W\!\equiv\!ab\ [c]$ s'écrit comme un produit $W\!=\!UV$ avec  $U\!\equiv\!a\ [c]$ et $V\!\equiv\!b\ [c]$.  Or, si $\mbox{pgcd}(ab,c)\!=\!1$, le théorème de la progression arithmétique nous dit qu'il existe un nombre premier $W\!\equiv\!ab\ [c]$ ce qui implique que $U$ ou $V$ est égal à $\pm1$ et on est dans le cas trivial mentionné précédemment.

jandri

@gebrane
Ton équation a une septième solution dans $\N^2$, la solution $(0,0)$.

gebrane

Lol, j'ai oublié cette solution triviale. Merci @jandri
 Les autres sont sauf erreurs. 

(x,y)= (24,6),  (14,7), ( 9,9), ( 8,10), ( 6,15) ( 5, 25)
La résolution n'est pas si simple, celui qui essaiera le sentira

Une absence sentie de @AD, j'espère qu'il va bien 

zygomathique

@gebrane :

$xy = 5x + 4y \iff (x- 4)(y - 4) = x + 16 \Longrightarrow (x + 1)y \equiv 0  [5] \iff (x \equiv 4[5]) \text{ou} (y \equiv 0 [5]) $

supposons y = 5k alors $kx = x + 4k \iff (x - 4)(k - 1) = 4$

k = 0 => (x, y) = (0, 0)
k = 2 => (x, y) = (8, 10)
k = 3 => (x, y) = (6, 15)
k = 5 => (x, y) = (5, 25)

supposons x = 5k + 4 alors $ (5k + 4)y = 5(5k + 4) + 4y \iff ky = 5k + 4 \iff k(y - 5) = 4$

k = 1 => (x, y) = (9, 9)
k = 2 => (x, y) = (14, 7)
k = 4 => (x, y) = (24, 6)

JLT

gebrane a dit :

Amusement : Pour c=1, l'équation 4y + 5x = xy admet exactement 6 solutions dans $\N^2$

$(x-4)(y-5)=20$ donc $x-4$ est un diviseur de $20$ qui est plus grand ou égal à $-4$, d'où $x-4\in \{-4,-2,-1,1,2,4,5,10,20\}$. Les valeurs de $y-5$ sont respectivement $-5,-10,-20,20,10,5,4,2,1$ mais comme $y-5\geqslant -5$ on élimine la deuxième et la troisième solution.

Ben314159

En fait, en divisant par les pgcd de $(a,c)$ et de $(b,c)$, j'obtient ça dans le cas $c\!\not=\!0$ : 
$(a,b,c)$ est solution si et seulement si $\ \mbox{pgcd}(a,b,c)\!=\!1$ et $\big(a\equiv\pm\mbox{pgcd}(a,c)\ [c]$ ou $b\equiv\pm\mbox{pgcd}(b,c)\ [c]\big)$ 
EDIT : j'ai l'impression d'avoir oublié un truc.  La condition est effectivement nécessaire, mais pas suffisante.

depasse

Bonjour à tous les fâchés par la disparition assurément fortuite de mon dernier message, et aux autres.

Je démontre ma conjecture d'alors en prouvant, je l'espère, que

pour tout $(a,b,c)$ dans $\mathbb {Z \times \mathbb Z \times \mathbb Z^*} $,
  si $<a,b,c>(x,y):=ax+by+cxy$,
alors $<a,b,c>(\mathbb Z^2)=\mathbb Z$    SSI    $a$ ou $b$ est congru à $1$ ou $-1$ modulo $c$.

Plan de la preuve:
1. Cas $0\leq a \leq b \leq c/2$:
1.1 $1 \in \{a,b,c\} \Rightarrow <a,b,c>$ surjective.
1.2 $1 \not\in \{a,b,c\} $ et $ax+by+cxy=1\Rightarrow (a,b,c)=(b,b,2b+1)$
1.3 $1 \not\in \{a,b,c\} $ et $ (a,b,c)=(b,b,2b+1)\Rightarrow ax+by+cxy\neq -1$
1.4 Conclusion: $<a,b,c>$ surjective SSI $1 \in \{a,b,c\} $.
2.Cas général:
Notations:
$a_c$ (resp. $b_c ) \in ]-c/2,c/2] \cap c\mathbb Z+a$ (resp.$+b$);
$\alpha,  \beta, \gamma \in \{-1,1\}$.
2.1$<a,b,c>$ surjective SSI$<a_c,b_c,c>$ surjective.
2.2$<a,b,c>$ surjective SSI $<\alpha a,  \beta b, \gamma c>$surjective. 
2.3$<a,b,c>$ surjective SSI $<b,a,c>$ surjective.
2.4 Conclusion: $<a,b,c>$ surjective    SSI    $a$ ou $b$ est congru à $1$ ou $-1$ modulo $c$.

Si quelqu'un n'a pas enterré cet exercice et souhaite une démonstration plus détaillée, je serai ravi.
Cordialement
Paul

depasse

Bonjour
@etanche m'invite à détailler.

pour tout $(a,b,c)$ dans $\mathbb {Z \times \mathbb Z \times \mathbb Z^*} $,
  si $<a,b,c>(x,y):=ax+by+cxy$,
alors $<a,b,c>(\mathbb Z^2)=\mathbb Z$    SSI    $a$ ou $b$ est congru à $1$ ou $-1$ modulo $c$.

Plan de la preuve:
1). Cas $0\leq a \leq b \leq c/2$:
1.1) $1 \in \{a,b,c\} \Rightarrow <a,b,c>$ surjective.
     Pour tout $z$ et tout $(a,b,c)$
     $z= 1.z +b.0+c.z.0 =a.0+1.z+c.0.z=a.(1-b)+b.(z+ab-a)+1. (1-b).(z+ab-a)$
1.2) $1 \not\in \{a,b,c\} $ et $ax+by+cxy=1\Rightarrow (a,b,c)=(b,b,2b+1)$
      $c$ étant non nul, $<a,b,c>(x,y):=ax+by+cxy=1$ se réécrit $(cx+b)(cy+a)=c.1+ab$
1.2.1)$(cx+b)(cy+a)=|(cx+b)||(cy+a)|$ car $(cx+b)(cy+a)=c.1+ab >0$

1.2.2)$xy \neq 0$ (sinon $ax$ ou $by =1$: en contradiction avec $1 \not\in \{a,b,c\} $); 
1.2.3) $0<c+b\leq cx+b$ si $x>0$; de même $0<c+a\leq cy+a$ si $y>0$;
         $0>-c+b\geq cx+b$ si $x<0$; de même $0>-c+a\geq cy+a$ si $y<0$, soit
         $0<c-b\leq |cx+b|$ si $x<0$; de même $0<c-a\leq |cy+a|$ si $y<0$;
         finalement,  $|cx+b| \geq c-b$, $|cy+a| \geq c-a$,
         $c+ab=(cx+b)(cy+a)=|cx+b||cy+a|\geq (c-b)(c-a)=c(c-a-b)+ab$
         d'où $1\geq c-a-b$, soit
         $c\leq a+b+1$
1.2.4) or $a+b\leq c$. Donc $(a,b,c)=(b,b,2b)$ ou $(b,b,2b+1)$.
         $(b,b,2b)$ est exclu car $(b,b,2b)\neq1$ quand $b\neq 1$.
          Reste le cas $(b,b,2b+1)$.

1.3 $1 \not\in \{a,b,c\} $ et $ (a,b,c)=(b,b,2b+1)\Rightarrow ax+by+cxy\neq -1$:
       $ax+by+cxy= -1$ se réécrit ici $((2b+1)x+b)((2b+1)y+b)=-2b-1+b^2=(b-1)^2-2>0$ car $b\neq 1$ et $b\neq 0$ (car $c=2b+1\neq 1$).
        Donc $(2b+1)x+b$ et $(2b+1)y+b$ ont même signe et leurs valeurs absolues sont minorées par $b+1$.
        Or $(b+1)^2=b^2+2b+1>b^2-2b-1$.
CQFD
1.4 Conclusion: $<a,b,c>$ surjective SSI $1 \in \{a,b,c\} $.
2.Cas général:
Notations:
$a_c$ (resp. $b_c ) \in ]-c/2,c/2] \cap c\mathbb Z+a$ (resp.$+b$);
$\alpha,  \beta, \gamma \in \{-1,1\}$.
2.1$<a,b,c>$ surjective SSI$<a_c,b_c,c>$ surjective.
2.2$<a,b,c>$ surjective SSI $<\alpha a,  \beta b, \gamma c>$surjective. 
2.3$<a,b,c>$ surjective SSI $<b,a,c>$ surjective.
2.4 Conclusion: $<a,b,c>$ surjective    SSI    $a$ ou $b$ est congru à $1$ ou $-1$ modulo $c$.

Pardon pour de très probables erreurs, seulement des coquilles, j'espère
Cordialement
Paul

etanche

@ depasse tes solutions sont toujours impressionnantes.