Как доказать свойства о специфической модульной арифметической эквивалентности

Question

С тех пор, как я был представлен модульной арифметике, у меня были проблемы с этим.Я думаю, что он использует часть моего мозга, которую я не использовал часто.В любом случае, я думал об этой конкретной эквивалентности: $$ a ^ 3 \ equiv 5 \, (\ text {MOD} 7) $$ И у меня есть догадка, что нет $ a $ S.t.Эта эквивалентность верна.Имитация его, ясно, что есть шаблон: 6, 1, 6, 6, 0, 1, 1, 6, 1, 6, 6, 0, 1, 1, 6, 1,6, 6, 0 ...

Но я не могу выяснить, как формально доказать 1., что этот шаблон является фактическим шаблоном и в качестве расширения, 2. Что вышеуказанная эквивалентность не удерживается (оно должно быть тривиальным, если я могу доказать 1).

Может кто-нибудь помочь?Большое спасибо.

Answer 1

Вы можете доказать это, вычислев значение $ a ^ 3 \ bmod 7 $ для $ a= 0, 1,2,3,4,5,6 $ ; Если ни один из этих выходных 5, то вы доказали претензию.

Почему это достаточно? Ну, если $ a \ equiv b \ pmod 7 $ , то $ a ^ 3 \ equiv b ^ 3 \ pmod 7 $ . Итак, если произошло любое решение для $ a ^ 3 \ equiv 5 \ pmod 7 $ , то вы можете взять $ B= a \ bmod 7 $ , и это было бы другое решение. Теперь $ B $ является одним из $ 0,1,2,3,4,5,6 $ , Таким образом, мы доказали, что если есть какое-либо решение, то один из $ 0,1,2,3,4,5,6 $ должен быть решением. И наоборот, если ни один из $ 0,1,2,3,4,5,6 $ - это решение, то нет никакого решения вообще.

Для специального случая квадрата (а не кубики) вы можете заинтересовать в квадратичная взаимность , который является более продвинутой техникой, которая позволяет проверить наличие решений для такого уравнения. Есть также Кубическая взаимность , хотя я не уверен, приводит ли это к эффективному алгоритму Проверьте наличие решений, когда у вас есть кубик вместо квадрата.