Factorisation par différence de carrés : a² − b² pour n impair

Le calculateur de factorisation par différence de carrés reçoit un entier composé impair positif et trouve des entiers a et b tels que le carré de a moins le carré de b égale le nombre initial. Il renvoie aussi les facteurs non triviaux correspondants, puisque a² − b² vaut toujours (a − b)(a + b). La recherche commence près de la racine carrée : les facteurs obtenus sont donc aussi proches que possible et b est minimal. Les nombres pairs, les nombres premiers et 1 déclenchent une erreur explicite au lieu de la factorisation triviale 1 × n.

Transformez un nombre impair en deux carrés

L’identité algébrique a² − b² = (a − b)(a + b) relie une soustraction à la factorisation entière. Pour un entier composé impair n, toute paire de facteurs non triviaux contient deux nombres impairs. Si ces facteurs sont d et q, avec d ≤ q, alors a = (q + d) / 2 et b = (q − d) / 2.

Ces deux résultats sont entiers, car la somme et la différence de deux impairs sont paires. Le calculateur cherche d’abord un diviseur proche de la racine carrée de n, détermine son facteur complémentaire par division exacte, puis applique ces formules. Par exemple, 5959 possède la paire 59 × 101.

Leur demi-somme vaut 80 et leur demi-différence 21, d’où 80² − 21² = 6400 − 441 = 5959. La réponse contient n, a, b, les deux facteurs et une identité lisible. Le résultat constitue ainsi à la fois un calcul et une preuve concise, que vous pouvez vérifier en multipliant les facteurs ou en soustrayant les carrés.

Comprenez les résultats non triviaux et les erreurs

Tout entier positif impair admet formellement une différence de carrés si la paire 1 × n est autorisée : a vaudrait (n + 1) / 2 et b vaudrait (n − 1) / 2. Cette écriture ne révèle aucun facteur utile ; elle est donc volontairement exclue. Une réponse réussie exige deux facteurs supérieurs à un.

Ainsi, un nombre premier impair et le nombre 1 produisent une erreur d’entrée indiquant l’absence de décomposition non triviale. Les entiers pairs sont également refusés par le contrat, même si certains multiples de quatre peuvent être écrits comme différences de carrés : ce service vise précisément la factorisation des entiers impairs. Un carré parfait impair reste valide.

L’entrée doit être un entier positif fini respectant la limite publiée. Les décimales, valeurs négatives, chaînes incorrectes et valeurs excessives sont refusées, sans arrondi, troncature ni approximation.

Pourquoi la recherche est déterministe

L’algorithme part du plus grand entier impair inférieur ou égal à √n, puis teste les candidats impairs en ordre décroissant. Le premier diviseur exact rencontré est le plus grand facteur ne dépassant pas la racine carrée ; son complément est le plus petit facteur qui ne lui est pas inférieur. Il obtient donc la paire non triviale la plus rapprochée et la plus petite valeur non négative de b.

La boucle possède une borne inférieure fixe, tandis que l’entrée maximale déclarée limite le travail : elle ne peut pas continuer indéfiniment. Les calculs restent exacts dans l’intervalle d’entiers sûrs pris en charge. Le traitement ne contacte aucun service réseau, ne consulte aucune table de nombres premiers, ne lit pas l’heure, n’emploie aucun choix aléatoire et ne conserve aucun état entre les requêtes.

Il s’agit d’une division d’essai, pas d’un système général pour les très grands entiers : la plage bornée garantit une exécution pratique, et l’erreur explicite empêche de présenter 1 × n comme une factorisation pertinente d’un nombre premier.