Zadanie 5

2005
Etap III
★★★★★
Teoria liczb
Nierówność z liczbami pierwszymi
Treść zadania
Dane są różne liczby pierwsze pp, qq oraz takie dodatnie liczby całkowite aa, bb, że liczba aqa^q daje resztę 11 przy dzieleniu przez pp, a liczba bpb^p daje resztę 11 przy dzieleniu przez qq. Wykaż, że ap+bq>1\frac{a}{p} + \frac{b}{q} > 1.
Umiejętności (5)
Wymagane umiejętności:
Reszty z dzielenia
Podzielność
Badanie liczb pierwszych
Zdobywane umiejętności:
Reszty z dzielenia
Analiza przypadków
Wskazówki (0/4)
Wskazówka 1
Zauważ, że jeśli apa \ge p lub bqb \ge q, nierówność jest prawdziwa. Główna trudność leży w przypadku, gdy jednocześnie a<pa < p i b<qb < q.
Wskazówka 2
Aby rozwiązać zadanie, wykaż, że przypadek a<pa < p i b<qb < q jest niemożliwy, jeśli założymy, że a,b>1a,b > 1. Wykorzystaj Małe Twierdzenie Fermata.
Wskazówka 3
Z warunku aq1(modp)a^q \equiv 1 \pmod p i Małego Twierdzenia Fermata wynika, że rząd aa modulo pp musi dzielić qq i p1p-1. Co to oznacza, skoro a>1a>1 i qq jest liczbą pierwszą?
Wskazówka 4
Rząd aa modulo pp musi być równy qq, a rząd bb modulo qq musi być równy pp. Oznacza to, że qq dzieli p1p-1, a pp dzieli q1q-1. Czy te dwa warunki mogą być spełnione jednocześnie?
Prześlij rozwiązanie

Zaloguj się, aby przesłać swoje rozwiązanie

Zaloguj się