This is an inofficial mirror of http://metamath.tirix.org for personal testing of a visualizer extension only.

Metamath Proof Explorer

Theorem modprminveq

Description: The modular inverse of A mod P is unique. (Contributed by Alexander van der Vekens, 17-May-2018)

Ref Expression
Hypothesis modprminv.1 ⊢ 𝑅 = ( ( 𝐴 ↑ ( 𝑃 − 2 ) ) mod 𝑃 )
Assertion modprminveq ( ( 𝑃 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ ¬ 𝑃 ∥ 𝐴 ) → ( ( 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) ∧ ( ( 𝐴 · 𝑆 ) mod 𝑃 ) = 1 ) ↔ 𝑆 = 𝑅 ) )

Proof

Step Hyp Ref Expression
1 modprminv.1 ⊢ 𝑅 = ( ( 𝐴 ↑ ( 𝑃 − 2 ) ) mod 𝑃 )
2 elfzelz ⊢ ( 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) → 𝑆 ∈ ℤ )
3 zmulcl ⊢ ( ( 𝐴 ∈ ℤ ∧ 𝑆 ∈ ℤ ) → ( 𝐴 · 𝑆 ) ∈ ℤ )
4 2 3 sylan2 ⊢ ( ( 𝐴 ∈ ℤ ∧ 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) ) → ( 𝐴 · 𝑆 ) ∈ ℤ )
5 modprm1div ⊢ ( ( 𝑃 ∈ ℙ ∧ ( 𝐴 · 𝑆 ) ∈ ℤ ) → ( ( ( 𝐴 · 𝑆 ) mod 𝑃 ) = 1 ↔ 𝑃 ∥ ( ( 𝐴 · 𝑆 ) − 1 ) ) )
6 4 5 sylan2 ⊢ ( ( 𝑃 ∈ ℙ ∧ ( 𝐴 ∈ ℤ ∧ 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) ) ) → ( ( ( 𝐴 · 𝑆 ) mod 𝑃 ) = 1 ↔ 𝑃 ∥ ( ( 𝐴 · 𝑆 ) − 1 ) ) )
7 6 expr ⊢ ( ( 𝑃 ∈ ℙ ∧ 𝐴 ∈ ℤ ) → ( 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) → ( ( ( 𝐴 · 𝑆 ) mod 𝑃 ) = 1 ↔ 𝑃 ∥ ( ( 𝐴 · 𝑆 ) − 1 ) ) ) )
8 7 3adant3 ⊢ ( ( 𝑃 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ ¬ 𝑃 ∥ 𝐴 ) → ( 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) → ( ( ( 𝐴 · 𝑆 ) mod 𝑃 ) = 1 ↔ 𝑃 ∥ ( ( 𝐴 · 𝑆 ) − 1 ) ) ) )
9 8 pm5.32d ⊢ ( ( 𝑃 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ ¬ 𝑃 ∥ 𝐴 ) → ( ( 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) ∧ ( ( 𝐴 · 𝑆 ) mod 𝑃 ) = 1 ) ↔ ( 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) ∧ 𝑃 ∥ ( ( 𝐴 · 𝑆 ) − 1 ) ) ) )
10 1 prmdiveq ⊢ ( ( 𝑃 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ ¬ 𝑃 ∥ 𝐴 ) → ( ( 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) ∧ 𝑃 ∥ ( ( 𝐴 · 𝑆 ) − 1 ) ) ↔ 𝑆 = 𝑅 ) )
11 9 10 bitrd ⊢ ( ( 𝑃 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ ¬ 𝑃 ∥ 𝐴 ) → ( ( 𝑆 ∈ ( 0 ... ( 𝑃 − 1 ) ) ∧ ( ( 𝐴 · 𝑆 ) mod 𝑃 ) = 1 ) ↔ 𝑆 = 𝑅 ) )