icone-challenge-math-OS

Solution pour le challenge 2


Notons S le segment d’extrémités \left(0,0\right) et \left(p,q\right) et notons d=p\wedge q.

Par homogénéité du pgcd, il existe des entiers P et Q premiers entre eux tels que :

    \[ p=Pd\qquad\text{et}\qquad q=Qd\]

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 :

    \begin{eqnarray*}\text{card}\left(S_{x}\right)&=&p+1\\\text{card}\left(S_{y}\right)&=&q+1\end{eqnarray*}

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\llbracket0,p\rrbracket\times\llbracket0,q\rrbracket tels que pb=qa, c’est-à-dire Pb=Qa.

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

Il existe donc k\in\llbracket0,d\rrbracket tel que a=kP, d’où b=kQ.

Ainsi : S_{x}\cap S_{y}=\left\{\left(kP,kQ\right);\thinspace k\in\llbracket0,d\rrbracket\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)\\& = & (p+1)+(q+1)-(d+1)\\& = & \boxed{p+q-p\wedge q+1}\end{eqnarray*}


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

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire