Çözüldü Sayılar Teorisi - Diyofant Denklemlerde Genel Çözüm - Öklit Algoritması - Programlama

Cornell University'den çözümlü bir örneğin AYT uyarlaması:

49x + 9y = 1 denklemini tam sayılar kümesinde sağlayan x ve y değerlerinin toplamını veren en küçük iki basamaklı doğal sayı kaçtır?

A) 11
B) 23
C) 49
D) 56
E) 62

a = 49, b = 9, EKOK(49, 9) = 1 = d, c = 1, d | c
Özel (Particular) çözüm olan x0 = -2 ve y0 = 7 Öklit Algoritmasıyla aşağıdaki gibi bulunur:

https://i72.servimg.com/u/f72/19/97/10/39/diopha10.png
http://pi.math.cornell.edu/~jerison/prelim1-solutions.pdf (Soru 1.b)

u = x - (-2) = x + 2....(I) ve v = y - 11....(II) dönüşümlerine göre homojen 49·u + 9·v = 0 denkleminin çözümü n ∈ Z olmak üzere u = -9·n ve v = 49·n olup sırasıyla (I) ve (II) eşitlikleri kullanılarak;
x + 2 = -9·n ⇒ x = -9·n - 2....(III)
y - 11 = 49·n ⇒ y = 49·n + 11....(IV)
(III) ve (IV) taraf tarafa toplanıp x + y = 40·n + 9 ve n = 1 için Minimum_İki_Basamaklı(x + y) = 40·1 + 9 = 49.

Kaynak:
https://math.libretexts.org/Courses/Mount_Royal_University/MATH_2150:_Higher_Arithmetic/5:_Diophantine_Equations/5.1:_Linear_Diophantine_Equations
https://math.libretexts.org/Courses...ber_Theory/8.03:_Linear_Diophantine_Equations
https://www.tutorialspoint.com/disc...atics_solving_linear_diophantine_equation.htm

Not: n = 0 için (III) ve (IV) eşitliklerine göre x = -2 ve y = 11 olmaktadır.

University of Utah'dan çözümlü bir örnek:

https://i72.servimg.com/u/f72/19/97/10/39/utah18.png

Fortran Çözümü:

https://i72.servimg.com/u/f72/19/97/10/39/utah_f11.png
https://www2.math.utah.edu/~treiberg/M3015_M1soln.pdf
[ Sayfa 5 - 6, Soru 5.(b) ]

Program:

Kod:

! Given integers a, b, and c, write a Fortran program to first check if
! the Diophantine equation ax + by = c has a solution. If solutions
! exist, the program will find a particular solution set for x and y,
! as well as the general solution based on another integer k that can
! take any value.

! Program written by the AI at https://codingfleet.com/code-generator/fortran/
! and modified by me, especially adding the "RECURSIVE" statement.
! Moreover, formatted output up to five digit integers are handled, and
! if bigger integer coefficients are needed, the number "5" in the 110th
! line "10 format(7(a,i5))" must be increased accordingly.

MODULE diophantine_utils
  IMPLICIT NONE

CONTAINS

  !> @brief Calculates the Greatest Common Divisor (GCD) of two integers
  !>        and finds coefficients x and y such that a*x + b*y = gcd(a,b).
  !> @param a_in The first integer.
  !> @param b_in The second integer.
  !> @param x    Output: Coefficient for a_in.
  !> @param y    Output: Coefficient for b_in.
  !> @return The GCD of a_in and b_in.
  RECURSIVE FUNCTION extended_gcd(a_in, b_in, x, y) RESULT(g)
    INTEGER, INTENT(IN) :: a_in, b_in
    INTEGER, INTENT(OUT) :: x, y
    INTEGER :: g, a, b
    INTEGER :: x1, y1
    INTEGER :: sign_a, sign_b

    ! Store original signs and work with absolute values for the core algorithm
    sign_a = 1
    sign_b = 1
    IF (a_in < 0) THEN
      a = -a_in
      sign_a = -1
    ELSE
      a = a_in
    END IF
    IF (b_in < 0) THEN
      b = -b_in
      sign_b = -1
    ELSE
      b = b_in
    END IF

    IF (b == 0) THEN
      ! Base case: gcd(a, 0) = a.
      ! a*1 + 0*0 = a
      g = a
      x = 1
      y = 0
    ELSE
      ! Recursive step: extended_gcd(b, a mod b, x1, y1)
      ! We know b*x1 + (a mod b)*y1 = gcd(b, a mod b) = gcd(a, b)
      ! Substitute a mod b = a - (a/b)*b
      ! b*x1 + (a - (a/b)*b)*y1 = g
      ! a*y1 + b*(x1 - (a/b)*y1) = g
      g = extended_gcd(b, MOD(a, b), x1, y1)
      x = y1
      y = x1 - (a / b) * y1 ! Integer division (a/b)
    END IF

    ! Adjust x and y based on the original signs of a_in and b_in
    ! If a_in was negative, we need -x for -a_in * (-x)
    ! If b_in was negative, we need -y for -b_in * (-y)
    x = x * sign_a
    y = y * sign_b

  END FUNCTION extended_gcd

END MODULE diophantine_utils


PROGRAM diophantine_solver
  USE diophantine_utils
  IMPLICIT NONE

  INTEGER :: a, b, c
  INTEGER :: g                          ! GCD of a and b
  INTEGER :: x_particular, y_particular ! A particular solution (x_p, y_p)
  INTEGER :: x_gcd, y_gcd               ! Coefficients for a*x_gcd + b*y_gcd = g

  ! Prompt user for input
  WRITE(*,*) "---------------------------------------------------"
  WRITE(*,*) "  Linear Diophantine Equation Solver: ax + by = c"
  WRITE(*,*) "---------------------------------------------------"
  WRITE(*,*) "Enter integer a:"
  READ(*,*) a
  WRITE(*,*) "Enter integer b:"
  READ(*,*) b
  WRITE(*,*) "Enter integer c:"
  READ(*,*) c

  ! Handle trivial case where a and b are both zero
  IF (a == 0 .AND. b == 0) THEN
    IF (c == 0) THEN
      WRITE(*,*) ""
      WRITE(*,*) "Equation: 0x + 0y = 0."
      WRITE(*,*) "This equation has infinitely many solutions (any integers x and y)."
    ELSE
      WRITE(*,*) ""
      WRITE(6,10) "Equation: 0x + 0y =", c, "."
      WRITE(*,*) "This equation has no solutions."
    END IF
    STOP
  END IF

10 format(7(a,i5))
! Up to 5-digit integer coefficients. If integers that have more digits
! are required, the number 5 must be increased accordingly.

  ! Calculate GCD and coefficients for a*x_gcd + b*y_gcd = g
  g = extended_gcd(a, b, x_gcd, y_gcd)

  WRITE(*,*) ""
  WRITE(*,*) "Calculations:"
  !WRITE(*,*) "  GCD(", a, ",", b, ") =", g
  WRITE(6,10) "  GCD(", a, ",", b, ") =", g
  WRITE(6,10) "  From Extended Euclidean Algorithm: ", a, "*", x_gcd, " + ", b, "*", y_gcd, " = ", g

  ! Check if a solution exists
  IF (MOD(c, g) /= 0) THEN
    WRITE(*,*) ""
    WRITE(*,*) "Result:"
    WRITE(6,10) "  No integer solutions exist for the equation ", a, "x + ", b, "y = ", c, "."
    WRITE(6,10) "  Reason: ", c, " is not divisible by GCD(", a, ",", b, ") which is ", g, "."
  ELSE
    ! Calculate a particular solution (x_p, y_p)
    ! We have a*x_gcd + b*y_gcd = g
    ! To get a*x + b*y = c, we multiply by (c/g)
    ! x_p = x_gcd * (c/g)
    ! y_p = y_gcd * (c/g)
    x_particular = x_gcd * (c / g)
    y_particular = y_gcd * (c / g)

    WRITE(*,*) ""
    WRITE(*,*) "Result:"
    WRITE(6,10) "  Integer solutions exist for the equation ", a, "x + ", b, "y = ", c, "."
    WRITE(*,*) ""
    WRITE(*,*) "  A particular solution (x_p, y_p) is:"
    WRITE(6,10) "    x_p =", x_particular
    WRITE(6,10) "    y_p =", y_particular
    WRITE(6,10) "  (Check: ", a, "*", x_particular, " + ", b, "*", y_particular, " = ", &
                a*x_particular + b*y_particular, " which equals ", c, ")"

    ! Present the general solution
    WRITE(*,*) ""
    WRITE(*,*) "  The general solution is given by:"
    ! The formulas for general solution are:
    ! x = x_p + (b/g) * k
    ! y = y_p - (a/g) * k
    ! These formulas correctly handle cases where a or b is zero (but not both, handled above).
    ! For example, if b=0, then b/g = 0, so x = x_p.
    ! If a=0, then a/g = 0, so y = y_p.
    WRITE(6,10) "    x = ", x_particular, " + (", b/g, ") * k"
    WRITE(6,10) "    y = ", y_particular, " - (", a/g, ") * k"
    WRITE(*,*) "  where k is any integer."

  END IF

END PROGRAM diophantine_solver