Arithmétique

[inviteab2b41c6]

Salut,
j'ai un petit exo d'arithmétique plutôt visuel, mais assez intéressant, je vais essayer de le poster quand même...

On prend 2vecteurs de Z² u et v.
On considère le parallelogramme que dessinent u et v.

La première question est de savoir combien de points de Z² seront dans ce parallelogramme.
La seconde question est plus visuelle:
On prend un vecteur k quelconque,on l'additionne par lui même jusqu'à ce qu'il ne soit plus dans notre parallelogramme.
Dès qu'il sort, on peut le ramener dans le parallelogramme de la facon suivante:

S'il sort par le haut, on considere alors que le parallelogramme s'est déplacé, l'ancienne bordure du haut devient la bordure du bas.
De meme, si le parallelogramme sort par la droite, on considère que la bordure de droite devient la bordure de gauche du nouveau parallelogramme.

On considère alors les nouvelles coordonnées, par rapport au point en bas à gauche.

En fait, une question intéressante (et sur laquelle je plenche également, même si je pense avoir la réponse...) est de savoir, en fonction de p et de k, quelle est la représentation de notre groupe...

Par exemple, dans le cas où u et v forment un rectangle de longueur p et de hauteur k, alors le groupe ainsi formé n'est autre que (Z/kZ)^p.
-----

[shokin]

Je suppose que les sommets du parallélogramme sont situés également dans Z^2.

Je suppose également que nous sommes dans un repère orthonormé (même si ça marche aussi dans un repère non orthonormé).

Je considère les vecteurs z compris dans Z^2.


Combien y a-t-il de points de Z^2 dans le vecteur z(a;b) ?

il y en a m, m=pgdc(IaI;IbI)+1. (IaI étant la valeur absolue de a.)

Si a=0, m=IbI+1.
Si b=0, m=IaI+1.


Combien y a-t-il de points dans un rectangle ?

Un rectangle sera formé par les vecteurs z1(a1;0) et z2(0;b2), avec a1 et b2 entiers non nuls.

Comme z1 et z2 sont orthogonaux, le rectangle contiendra (Ia1I+1)(Ib2I+1) points de Z^2.


Combien y a-t-il de points sur la diagonale du rectangle ?

soit z12 le vecteur somme des vecteurs v1 et v2. z12=(a1;b2).

Il y a donc m points de z^2 sur ce vecteur, m=pgdc(Ia1I;Ib2I)+1.

Donc dans un triangle rectangle, il y a n points de z^2.

n=[(Ia1I+1)(Ib2I+1)+m]/2


Si deux polygones sont collés par un côté commun, le nombre de points de Z^2 compris dans le nouveau polygone égale la somme des nombres de points compris dans les deux polygones moins le nombre de points situés sur le côté.

Par conséquent, si au polygone A, j'enlève un polygone B ayant une côté commun avec A, le nouveau polygone C aura p(C) points dans Z^2. p(C)=p(A)-p(B)+n, avec n nombre de points de Z^2 situés sur ce côté commun.


Combien y a-t-il de points dans un triangle dont les sommes se situent dans Z^2 avec un côté vertical ou horizontal ?

Soit le triangle formé par les vecteurs v1=(a1;b1), v2=(a2;b2) et v1+v2, avec v1 horizontal (donc b1=0).

Si a1 et a2 sont de signes opposés, le triangle formé peut être considéré comme somme de deux triangles rectangles (celui formé par (a1-b1;0) et (0;b2) et leur somme et celui formé par (a2;0) et (0;b2) et leur somme.

Si a1 et a2 sont de même signe, le triangle formé peut être considéré comme différence de ces deux triangles.

Combien y a-t-il de points de Z^2 dans un parallélogramme ?


Tout parallélogramme peut être obtenu en deux étapes à partir d'un rectangle.

1. Dans un rectangle, je déplace un triangle rectangle (dont un des côtés est côté du rectangle) qui vient s'accoler au côté opposé.

Le nombre de points compris dans le triangle reste le même, où que soit posé le triangle.

Pour passer du rectangle au parallélogramme intermédiaire, pour trouver le nombre de points que celui-ci contient, le nombre de points "intérieurs"(non situé sur les côtés) n'a pas changé. Seul changement : les deux côtés opposés du rectangle ont été remplacés par les hypoténuses égales du triangle et de son image. Il faut alors simplement soustraire deux fois le nombre de points de Z^2 contenus dans le côté en question (qui a disparu), puis ajouter deux fois le nombre de points de Z^2 contenus dans le nouveau côté.

2. Deuxième tranformation similaire, sauf que le côté qui disparaît n'est pas forcément horizontal ou vertical.

[Je laisse le soin de transformer cela en formule.]

Donc si tu as un parallélogramme formé par les vecteurs u et v, tu peux raisonner comme celui-ci étant obtenu comme dit précédemment.

Ou tu peux considérer le rectangle aux côtés horizontaux comprenant ce parallélogramme et soustraire les triangles...



Shokin

[invite8f53295a]

Par exemple, dans le cas où u et v forment un rectangle de longueur p et de hauteur k, alors le groupe ainsi formé n'est autre que (Z/kZ)^p.

Salut,

C'est bizarre, personnellement je dirai plutôt que c'est (Z/kZ)x(Z/pZ)... Je m'explique : (je suppose aussi que u et v sont linéairement indépendants).
Le groupe dont tu parles est en fait le quotient de Z^2 par le sous-groupe engendré par u et v. Comme u et v sont linéairement indépendants ils engendrent un sous-groupe abélien libre de Z^2. D'après le thm de la base adapté, on peut trouver une base (e,f) de Z^2 dans laquelle u=ae et v=bf avec b|a. Le quotient est alors isomorphe à Z/aZ x Z/bZ. Pour déterminer a et b explicitement on peut procéder comme suit : b est le pgcd des éléments de la matrice de (u,v) dans n'importe quelle base. En effet c'est trivial dans la base (e,f), et il suffit de voir que le pgcd des éléments d'une matrice de M_2(Z) est invariant par conjugaison par GL_2(Z), c'est donc vrai également dans la base canonique. Pour trouver a il suffit de voir que ab est égal au déterminant...
Donc si tu veux trouver la classe d'isomorphisme de ton groupe, tu n'as pas besoin de déterminer la base (e,f) !

Exemple : u=(2,1) v=(1,4). La matrice de (u,v) est
Le pgcd de ses coefficients est 1 et son déterminant 10 donc le groupe est isormophe à Z/10Z.

[shokin]

Donc si tu veux trouver la classe d'isomorphisme de ton groupe, tu n'as pas besoin de déterminer la base (e,f) !

Tout à fait !

Shokin

[A voir en vidéo sur Futura]

[inviteab2b41c6]

Salut,
tu résumes en disant que c'est trivial ce que j'ai mis 30minutes à trouver hier en tatonnant
Mais oui c'est ca
Le coup du détérminant m'avais impressioné...

[shokin]

Exemple : u=(2,1) v=(1,4). La matrice de (u,v) est
Le pgcd de ses coefficients est 1 et son déterminant 10 donc le groupe est isormophe à Z/10Z.

Ya quoi de juste là dedans ?

Je ne pense pas que le problème soit simple. Je me demande s'il existe une formule générale pour tous vecteurs u et v (j'envisage même qu'il n'y en ait pas ).

Sinon comment trouver une méthode spécialement pour le parallélogramme (autre que mes explications justes et incomplètes et détournées) ?

Décomposer le parallélogramme (comme tout autre polygone) en triangles rectangles et rectangles ? (en prenant soin de ne pas compter deux fois les mêmes points des côtés et sommets)

Compter le nombre de points sur chacune des droites verticales (ou horizontales) et les additionner ?

...

Pour l'instant, je peux affirmer sans crainte le nombre de points compris dans un rectangle, dans un triangle rectangle avec une formule simple que j'ai énoncée précédemment.

Avec z1(a1;0) et z2(0;b2).

Comme z1 et z2 sont orthogonaux, le rectangle contiendra (Ia1I+1)(Ib2I+1) points de Z^2.

Donc dans un triangle rectangle, il y a n points de z^2.

n=[(Ia1I+1)(Ib2I+1)+m]/2

Alors dans un parallélogramme avec deux côtés horizontaux,

soient alors ses deux vecteurs u(u1;0) et v(v1;v2)

Comme ce parallélogramme n'est rien d'autre qu'un rectangle (aux vecteurs u(u1;0) et v(0;v2) ) auquel on a déplacé un triangle, le nombre de points intérieurs (non situés sur les côtés) ne change pas (l'aire du triangle reste inchangée, translation oblige).

Il faut alors au nombre de points dans Z^2 du rectangle :

ajouter deux fois le nombre de points situés sur v(v1;v2)

enlever deux fois le nombre de points situés sur v(0;v2)

et l'on obtient le nombre de points de ce parallélogramme.

Le parallélogramme obtenu a (Iu1I+1)(Iv2I+1) + 2*(m+1) - 2*(v2+1), m étant le pgdc entre v1 et v2.


Reste maintenant à obtenir un parallélogramme (sans côté verticaux ou horizontaux).

Soit le parallélogramme formé par u(u1;u2) et v(v1;v2) avec u1, u2, v1, v2 entiers non nuls. (Si l'un est nul, l'on revient au point précédent.)

Nous allons faire le processus inverse afin de déterminer le (un) rectangle (ses vecteurs) de départ.

Disons que u1>=v1 (si v1>=u1, il suffit d'inverser les rôles).

Alors le triangle formé par les vecteurs a(v1;v2) et b(0;[v1*u2/u1]-v2) et leur somme est déplacé de l'autre côté du parallélogramme pour former un nouveau parallélogramme (avec deux côtés verticaux) dont les vecteurs directeurs sont :

c(u1;u2) et d(0;[v1*u2/u1]-v2)

Ce parallélogramme a été obtenu à partir du rectangle déterminé par les vecteurs :

e(u1;0) et d(0;[v1*u2/u1]-v2)

Le nombre de points de Z^2 compris dans ce rectangle est :

(u1+1)*(E([v1*u2/u1]-v2)+1)

Pour obtenir le nombre de points de Z^2 compris dans le parallélogramme de départ, il faut :

ajouter deux fois le nombre de points compris dans u
ajouter deux fois le nombre de points compris dans v
retrancher deux fois le nombre de points compris dans d
retrancher deux fois le nombre de points compris dans e

Ce qui donne :

(u1+1)*(E([v1*u2/u1]-v2)+1)
+ 2*( pgdc(u1;u2)+1 )
+ 2*( pgdc(v1;v2)+1 )
- 2*( E([v1*u2/u1]-v2)+1 )
- 2*( u1+1)

=p, p étant donc le nombre de points compris dans mon parallélogramme.

Si j'ai fait juste,

c'est aussi valable si v1>=u1
on peut poser u2>=v2 ou v2>=u2 puis adapter.

Heu... vérifiez...

Shokin

[invite8f53295a]

Ca me semble quand même beaucoup plus simple de compter les points en choisissant une base convenable au moyen du thm de la base adaptée non ?

[invite8f53295a]

tu résumes en disant que c'est trivial ce que j'ai mis 30minutes à trouver hier en tatonnant

J'ai pas dit que c'était trivial, c'est non trivial le thm de la base adaptée...

[shokin]

La seconde question est plus visuelle:
On prend un vecteur k quelconque,on l'additionne par lui même jusqu'à ce qu'il ne soit plus dans notre parallelogramme.
Dès qu'il sort, on peut le ramener dans le parallelogramme de la facon suivante:

S'il sort par le haut, on considere alors que le parallelogramme s'est déplacé, l'ancienne bordure du haut devient la bordure du bas.
De meme, si le parallelogramme sort par la droite, on considère que la bordure de droite devient la bordure de gauche du nouveau parallelogramme.

On considère alors les nouvelles coordonnées, par rapport au point en bas à gauche.

Il me semble que la base importe peu, que ses axes soient orthogonaux ou non, que ses vecteurs unités aient même norme ou non. On peut considérer deux vecteurs quelconques non colinéaires qui déterminent la base.

Alors autant considérer la base la plus simple, celle orthonormée (vecteurs unités orthogonaux et aux normes égales à 1, u(1;0) et v(0;1)).

Le point de départ d'un vecteur w(w1;w2) sera donc situé dans le carré (formé u et v, le coin en bas à gauche étant le point origine O(0;0). Soit P(p1;p2) ce point de départ, 0=<p1<1 et 0=<p2<1.

Le point d'arrivée sera tout simplement z(z1;z2) avec :

z1=PF(p1+w1)
z2=PF(p2+w2)

PF signifiant part fractionnaire (Soit m=PE(m)+PF(m) pour tout m réel posifit).

En fait, une question intéressante (et sur laquelle je plenche également, même si je pense avoir la réponse...) est de savoir, en fonction de p et de k, quelle est la représentation de notre groupe...

Par exemple, dans le cas où u et v forment un rectangle de longueur p et de hauteur k, alors le groupe ainsi formé n'est autre que (Z/kZ)^p.

Là, je n'ai du tout compris. Que veut dire "un rectangle de longueur p" ?

Qu'est-ce que la "représentation de notre groupe" ?

Shokin

[inviteab2b41c6]

Salut,
en fait on se rend compte que l'on peut trouver également notre groupe, en passant par des opérations élémentaires sur la matrice.
Pour reprendre notre exemple:
(21)
(14)
j'échange les colonnes:
(12)
(41)
C2<- -2C1+C2
(1 0)
(4 -7)
L2<- L2-4L1

(1 0)
(0 -7)
En mutlipliant par -1 la dernier colonne on trouve
(10)
(07)

Le groupe est isomorphe à Z1xZ7 soit Z7