Python & Congruence modulo n

 Congruence modulo n : résolution d'une équation générale

Introduction

La congruence modulo n est un concept mathématique qui permet de déterminer si deux nombres sont égaux lorsqu'on les divise par un troisième nombre. Dans cet article, nous allons voir comment utiliser la congruence modulo n pour résoudre une équation générale de la forme \(x^2 + bx \equiv r [n]\).

Congruence modulo n

Deux nombres a et b sont congruents modulo n si leur différence est un multiple de n. En d'autres termes, a et b sont congruents modulo n si, lorsqu'on les divise par n, on obtient le même reste.

Par exemple, 3 et 8 sont congruents modulo 5 car leur différence, 5, est un multiple de 5. En effet, 5 = 1 × 5.

Résolution d'une équation générale

Pour résoudre une équation générale de la forme \(x^2 + bx \equiv r [n]\), nous allons utiliser le concept de congruence modulo n.

Créer un tableau de congruence

La première étape consiste à créer un tableau de congruence. Ce tableau contient toutes les valeurs possibles de x de 0 à n-1, ainsi que les restes de la division de \(x^2 + bx - r\) par n.

\(x\)	0	1	2	...	n-1
\(y=x^2 + bx - r\)	$$y_{0}$$	$$y_{1}$$	$$y_{2}$$	...	$$y_{n-1}$$

En jaune les valeurs de \(x\) et en vert le reste de la division y par n.

Rechercher les solutions

La deuxième étape consiste à rechercher les solutions de l'équation dans le tableau de congruence. Les solutions sont les valeurs de x pour lesquelles le reste de la division de \(x^2 + bx - r\) par n est égal à zéro.

1. Afficher les solutions

La troisième étape consiste à afficher les solutions de l'équation.

Exemple

Résolvons l'équation \(x^2 \equiv -1 [25]\).

Créer un tableau de congruence

\(x\)	...	7	8	...	24
\(y=x^2 + 1\)	...	0	15	...	2

Le rouge indique la solution 

Rechercher les solutions

Les solutions de l'équation sont les valeurs de x pour lesquelles le reste de la division de \(x^2 + 1\) par 25 est égal à zéro. En regardant le tableau de congruence, on voit que les solutions sont :

• x = 7
• x = 18

Afficher les solutions

Les solutions de l'équation \(x^2 \equiv -1 [25]\) sont donc :

$$x = \{25k+7, 25k+18\}$$

Code Python

Voici le code Python pour résoudre l'équation générale \(x^2 + bx \equiv r [n]\) :

def congruence_modulo_n(a, b, n):
  """
  Vérifie si a est congrue à b modulo n.

  Args:
    a: Le premier nombre.
    b: Le deuxième nombre.
    n: Le module.

  Returns:
    True si a est congrue à b modulo n, False sinon.
  """

  return (a - b) % n == 0


def resoudre_congruence(b, r, n):
  """
  Résout l'équation générale x^2 + bx ≡ r [n].

  Args:
    b: Le coefficient de x.
    r: Le terme constant.
    n: Le module.

  Returns:
    Les solutions de l'équation.
  """

  # Créer un tableau de congruence
  tableau_congruence = [[i, (i**2 + b*i - r) % n] for i in range(n)]

  # Rechercher les solutions dans le tableau de congruence
  solutions = [x[0] for x in tableau_congruence if x[1] == 0]

  # Renvoyer les solutions
  return solutions


# Demander à l'utilisateur de saisir les valeurs de b, r et n
b = int(input("Entrez la valeur de b : "))
r = int(input("Entrez la valeur de r : "))
n = int(input("Entrez la valeur de n : "))

# Résoudre l'équation générale
solutions = resoudre_congruence(b, r, n)

# Afficher les solutions
print(f"Les solutions de l'équation x^2 + {b}x ≡ {r} [{n}] sont : {solution}".)

Conclusion

Dans cet article, nous avons vu comment utiliser la congruence modulo n pour résoudre une équation générale de la forme \(x^2 + bx \equiv r [n]\). Nous avons également vu un exemple pour illustrer la méthode et fourni le code Python pour résoudre l'équation.