Theorem modprminv

Description: Show an explicit expression for the modular inverse of A mod P . This is an application of prmdiv . (Contributed by Alexander van der Vekens, 15-May-2018)

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

Proof

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