Home

MPSI/PCSI

Maths

Analyse

Logique

Dans cette vidéo, Paul propose un exercice de logique où l'on doit démontrer que si n est la somme de 2 carrés alors le reste de la division euclidienne de n par 4 est toujours différent de 3. Il utilise la méthode de récurrence mais constate qu'elle ne sert à rien dans ce cas précis. Il cherche alors à séparer les 4 cas possibles et arrive à démontrer que r sera toujours différent de 3. Il utilise l'unicité de la division euclidienne pour prouver que q et r sont comme il le souhaite. En fin de compte, il démontre cette propriété et conclut l'exercice.

Salut c'est Paul et on se retrouve dans cette nouvelle vidéo où on va parler d'un exercice sur la logique toujours où vous êtes un peu lâché au crocodile, où vous devez trouver la réponse à un exercice et où il n'y a aucune indication sur comment vous allez y arriver. Mais on va y arriver ensemble. Donc le fait est de démontrer que si n est la somme de 2 carrés alors le reste de la division euclidienne de n par 4 est toujours différent de 3. Donc qu'est-ce que ça veut dire? C'est que la division euclidienne de n par 4, déjà c'est n, l'écriture n égale 4q plus r, avec le reste étant r ici, et on veut quand n égale la somme de 2 carrés, donc ici m carrés plus p carrés, que r soit toujours différent de 3. Donc comment on va prouver ça? On pourrait dire par récurrence. Il y a des n, c'est pour toutes n. Donc on va tester ça pour voir. Si on prend n plus 1 avec m carrés plus p carrés, on va essayer de faire apparaître n. Donc n égale p carrés plus m carrés moins 1. Il va falloir prouver que c'est la somme de 2 carrés, dans plein de cas ça ne va pas l'être, donc on ne va pas pouvoir appliquer pn. Et donc si on ne peut pas utiliser pn pour prouver pn plus 1, la récurrence ne sert à rien. Autant directement prouver la propriété tout de suite. Donc une division qui vienne par 4, ça veut dire aussi que r, c'est soit 0, soit 1, soit 2, soit 3. Donc en fait il n'y a que 4 cas possibles. Donc on peut imaginer faire une division sous le cas, après la question ça va être de trouver quel cas, comment séparer nos possibilités. Donc on va le voir tout de suite. Pour commencer l'exercice, on prend un n tel que n est la somme de 2 carrés, ici on les nomme p et m, notre carrés. Et on rappelle sur la division Euclidienne de a par b, c'est écrit, déjà elle existe, il y a unicité. Donc il existe des uniques qr entiers relatifs, tel que r, donc le reste, est compris entre 0 et b est strictement inférieur ou égal à b, et tel que a égal bq plus r. Donc voilà, ça vous donne par coeur ça. Donc maintenant on peut écrire la division Euclidienne de n par 4, avec q et r. Et en fait là, comment on va avoir nos 4 cas? Et bien le cas de cas ça va être m et p paire, m et p impaire, m paire p impaire et m paire p paire. Pourquoi je dis ça? En fait l'intuition c'est de dire que si on remplace m, déjà pour dans le cas paire, en fait ça va être particulièrement facile parce que si on remplace p ici, voilà, là dans le cas où on a justement du coup n égale la somme de m carrés plus p carrés, si on remplace m et p par leur valeur, donc 2k ici et 2j, parce qu'ils sont paires, et bien en fait on peut mettre k 4 en facteur, parce que 2 ici au carré, et donc on a 4 qui divise r, et donc r est égal à 0. Parce que donc 4 ici divise r, parce que si on met q ici de l'autre côté, voilà, on a 4 facteur de k carrés plus j carrés moins 1, qui est un entier relatif, donc r est égal à 4 fois un entier, donc 4 divise r. Sauf que comme r est strictement inférieur à 4, et bien est positif, la seule solution c'est que r soit égal à 0. Donc on a bien ici r différent de 3, c'est ce qu'il faut remarquer. Donc dans le cas où m et p sont impaires, m égale 2k plus 1 et p égale 2j plus 1, du coup on écrit ce que ça veut dire, c'est à dire que n ici, 4q plus r est égal à m au carré plus p au carré qui donne ça, si on développe. Et là on voit des 4 et des 1, ok? En fait là, si on met ce 4 ici de l'autre côté, en fait on peut factoriser par 2 ici. Par 2 ici, c'est égal à 1 plus 2 facteur de 1 plus 2 facteur de k carrés plus k plus j carrés plus j moins q, ok? Donc ici on a 2 qui divise r. Donc vu que r c'est soit égal à 0, 1, 2 ou 3, mais en fait r est égal à 0 ou 2, donc il est différent de 3. Et maintenant on a le cas où m est paire, p est impaire. Donc si m est paire et p est impaire, m est égal à 2k et p est égal à 2j plus 1. Donc on écrit ce que ça veut dire toujours avec n et m carré plus p carré. On factorise par 4 ce qu'on peut. En fait là on va pas pouvoir factoriser, on va pas pouvoir factoriser par 1, là le 1 il reste tout seul, on peut pas le factoriser. Donc on factorise par 4 et en fait là ce qu'on remarque c'est qu'en fait on fait apparaître la division euclidienne ici. 4 ici, on a notre q et on a notre r. Et pourquoi on peut dire que q ici est égal à ça et r est égal à 1? Parce qu'on a l'unicité de la division euclidienne. Donc si on arrive à écrire n sous la forme 4 fois 1 entier plus 1 reste qui est bien compris entre les bonnes valeurs, c'est que c'est notre division euclidienne. Donc r est égal à 1 dans ce cas là. Et finalement on a le cas p impaire et m impaire. Mais là on a déjà fait le travail parce qu'en fait si on remarque par symétrie des rôles de m et p. Parce qu'on dit, on invoque une règle de symétrie c'est qu'en fait p et m, on les a appelés p et m mais ils jouent le même rôle dans la somme des carrés. C'est juste arbitrairement on les a nommés comme ça. Donc en fait là le cas ici il a traité m paire et p impaire mais il a aussi traité le cas p. En fait ce cas il peut être généralisé comme étant un des nombres est paire et un des nombres est impaire. Et donc ça rentre aussi dans ce cas là. Donc par symétrie des rôles de m et p, r égal à 1. On revient dans le cas d'avant. Ainsi r est soit égal à 1, 0 ou 2. Donc r est différent de 3. Ainsi on a notre conclusion et on a fini l'exercice. Voilà c'est la fin et on se dit à la prochaine fois!

Disjonction et arithmétique

RELATED

Recommended videos

Utiliser les quantificateurs

Ecrire la négation

Equivalence et implication