icone-challenge-math-OS

Introduisons quelques notations. Notons :

  • S le segment d’extrémités \left(0,0\right) et \left(p,q\right)
  • d=p\wedge q (le pgcd de p et q)

Par homogénéité du pgcd, il existe des entiers p' et q' premiers entre eux tels que :

    \[ p=p'd\qquad\text{et}\qquad q=q'd\]

Notons S_{x} (resp. S_{y}) l’ensemble des points de S d’abscisse entière (resp. d’ordonnée entière). On cherche \text{card}\left(S_{x}\cup S_{y}\right).

Il est clair que :

    \[ \text{card}\left(S_{x}\right)=p+1\qquad\text{et}\qquad\text{card}\left(S_{y}\right)=q+1\]

Par ailleurs S_{x}\cap S_{y} est l’ensemble des points à coordonnées entières de S, à savoir les couples \left(a,b\right)\in\left\{0,\cdots,p\right\}\times\left\{0,\cdots,q\right\} tels que pb=qa, c’est-à-dire p'b=q'a.

D’après le théorème de Gauss, cette condition impose p'\mid a.

Il existe donc k\in\{0,\ldots,d\} tel que a=kp', d’où b=kq'.

Ainsi : S_{x}\cap S_{y}=\left\{\left(kp',kq'\right);\thinspace k\in\left\{0,\cdots,d\right\}\right\} et donc \text{card}\left(S_{x}\cap S_{y}\right)=d+1.

Finalement :

    \begin{eqnarray*}\text{card}\left(S_{x}\cup S_{y}\right) & = & \text{card}\left(S_{x}\right)+\mbox{card}\left(S_{y}\right)-\mbox{card}\left(S_{x}\cap S_{y}\right)\\& = & p+1+q+1-\left(d+1\right)\\& = & \boxed{p+q-p\wedge q+1}\end{eqnarray*}


Pour consulter l’énoncé, c’est ici

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu