icone-challenge-math-OS

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

Introduisons quelques notations :

  • 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éïté 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 \mbox{card}\left(S_{x}\cup S_{y}\right). Il est clair que :

    \[ \mbox{card}\left(S_{x}\right)=p+1\qquad\mbox{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\left\{ 0,\cdots,d\right\} tel que a=kp', d’où b=kq' en reportant. Ainsi : S_{x}\cap S_{y}=\left\{ \left(kp',kq'\right);\thinspace k\in\left\{ 0,\cdots,d\right\} \right\} et donc \mbox{card}\left(S_{x}\cap S_{y}\right)=d+1. Finalement :

    \begin{eqnarray*} \mbox{card}\left(S_{x}\cup S_{y}\right) & = & \mbox{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*}

Partager cet article
  •  
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu