# reszta kwadratowa

a = int(input("Podaj a -> liczba do sprawdzenia: "))
p = int(input("Podaj p -> liczba pierwsza modulo: "))


def potegowanieimod(b, k, n):
    y = 1
    while k > 0:
        if k & 1:
            y = y*b % n
        b = b**2 % n
        k = k >> 1
    return y


#Symbol Legendre'a
l = potegowanieimod(a, (p-1)//2, p)

if l == 0:
    print("a jest wielokrotnością p")
elif l == 1:
    print("a jest resztą kwadratową")
else:
    print("a nie jest resztą kwadratową")


# reszta kwadratowa to takie a ze istnieje x nalezące do Zp
# x^2 = a (mod p)