fantho69

x^x-y^x=p.py

Dec 23rd, 2022
818
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.13 KB | Science | 0 0
  1. # This program find the solutions of diophantine equation
  2. # x^x-y^y=p, p prime number
  3. # The theory show that the number of solution is limited to 7 triples x y p
  4. # x must be prime, y is equal to x-1, p must be of opportune form
  5. # the primality test is implemented using miller rabin algorithm
  6. P=500
  7. import random
  8. def power(x, y, p):
  9.     res = 1;
  10.     x = x % p;
  11.     while (y > 0):
  12.         if (y & 1):
  13.             res = (res * x) % p;
  14.         y = y>>1; # y = y/2
  15.         x = (x * x) % p;
  16.     return res;
  17. def miillerTest(d, n):
  18.     a = 2 + random.randint(1, n - 4);
  19.     x = power(a, d, n);
  20.     if (x == 1 or x == n - 1):
  21.         return True;
  22.     while (d != n - 1):
  23.         x = (x * x) % n;
  24.         d *= 2;
  25.         if (x == 1):
  26.             return False;
  27.         if (x == n - 1):
  28.             return True;
  29.     return False;
  30. def isPrime( n, k):
  31.     if (n <= 1 or n == 4):
  32.         return False;
  33.     if (n <= 3):
  34.         return True;
  35.     d = n - 1;
  36.     while (d % 2 == 0):
  37.         d //= 2;
  38.     for i in range(k):
  39.         if (miillerTest(d, n) == False):
  40.             return False;
  41.     return True;
  42. # Driver Code
  43. # Number of iterations
  44. k = 4;
  45. print("x y p")
  46. for x in range(2,P+1):
  47.     if(isPrime(x, k)):
  48.        if(isPrime(x**x-(x-1)**x, k)):
  49.             print(x,x-1,x**x-(x-1)**x)
  50.  
Advertisement
Add Comment
Please, Sign In to add comment