Theorem odzval 16695

Description: Value of the order function. This is a function of functions; the inner argument selects the base (i.e., mod 𝑁 for some 𝑁, often prime) and the outer argument selects the integer or equivalence class (if you want to think about it that way) from the integers mod 𝑁. In order to ensure the supremum is well-defined, we only define the expression when 𝐴 and 𝑁 are coprime. (Contributed by Mario Carneiro, 23-Feb-2014.) (Revised by AV, 26-Sep-2020.)

Assertion

Ref	Expression
odzval	⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → ((odℤ‘𝑁)‘𝐴) = inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝐴↑𝑛) − 1)}, ℝ, < ))

Distinct variable groups:   𝑛,𝑁   𝐴,𝑛

Proof of Theorem odzval

Dummy variables 𝑚 𝑥 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		oveq2 7349	. . . . . . . . 9 ⊢ (𝑚 = 𝑁 → (𝑥 gcd 𝑚) = (𝑥 gcd 𝑁))
2	1	eqeq1d 2732	. . . . . . . 8 ⊢ (𝑚 = 𝑁 → ((𝑥 gcd 𝑚) = 1 ↔ (𝑥 gcd 𝑁) = 1))
3	2	rabbidv 3400	. . . . . . 7 ⊢ (𝑚 = 𝑁 → {𝑥 ∈ ℤ ∣ (𝑥 gcd 𝑚) = 1} = {𝑥 ∈ ℤ ∣ (𝑥 gcd 𝑁) = 1})
4		oveq1 7348	. . . . . . . . 9 ⊢ (𝑛 = 𝑥 → (𝑛 gcd 𝑁) = (𝑥 gcd 𝑁))
5	4	eqeq1d 2732	. . . . . . . 8 ⊢ (𝑛 = 𝑥 → ((𝑛 gcd 𝑁) = 1 ↔ (𝑥 gcd 𝑁) = 1))
6	5	cbvrabv 3403	. . . . . . 7 ⊢ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} = {𝑥 ∈ ℤ ∣ (𝑥 gcd 𝑁) = 1}
7	3, 6	eqtr4di 2783	. . . . . 6 ⊢ (𝑚 = 𝑁 → {𝑥 ∈ ℤ ∣ (𝑥 gcd 𝑚) = 1} = {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1})
8		breq1 5092	. . . . . . . 8 ⊢ (𝑚 = 𝑁 → (𝑚 ∥ ((𝑥↑𝑛) − 1) ↔ 𝑁 ∥ ((𝑥↑𝑛) − 1)))
9	8	rabbidv 3400	. . . . . . 7 ⊢ (𝑚 = 𝑁 → {𝑛 ∈ ℕ ∣ 𝑚 ∥ ((𝑥↑𝑛) − 1)} = {𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)})
10	9	infeq1d 9357	. . . . . 6 ⊢ (𝑚 = 𝑁 → inf({𝑛 ∈ ℕ ∣ 𝑚 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < ) = inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < ))
11	7, 10	mpteq12dv 5176	. . . . 5 ⊢ (𝑚 = 𝑁 → (𝑥 ∈ {𝑥 ∈ ℤ ∣ (𝑥 gcd 𝑚) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑚 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < )) = (𝑥 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < )))
12		df-odz 16668	. . . . 5 ⊢ odℤ = (𝑚 ∈ ℕ ↦ (𝑥 ∈ {𝑥 ∈ ℤ ∣ (𝑥 gcd 𝑚) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑚 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < )))
13		zex 12469	. . . . . 6 ⊢ ℤ ∈ V
14	13	mptrabex 7154	. . . . 5 ⊢ (𝑥 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < )) ∈ V
15	11, 12, 14	fvmpt 6924	. . . 4 ⊢ (𝑁 ∈ ℕ → (odℤ‘𝑁) = (𝑥 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < )))
16	15	fveq1d 6819	. . 3 ⊢ (𝑁 ∈ ℕ → ((odℤ‘𝑁)‘𝐴) = ((𝑥 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < ))‘𝐴))
17		oveq1 7348	. . . . . 6 ⊢ (𝑛 = 𝐴 → (𝑛 gcd 𝑁) = (𝐴 gcd 𝑁))
18	17	eqeq1d 2732	. . . . 5 ⊢ (𝑛 = 𝐴 → ((𝑛 gcd 𝑁) = 1 ↔ (𝐴 gcd 𝑁) = 1))
19	18	elrab 3645	. . . 4 ⊢ (𝐴 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↔ (𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1))
20		oveq1 7348	. . . . . . . . 9 ⊢ (𝑥 = 𝐴 → (𝑥↑𝑛) = (𝐴↑𝑛))
21	20	oveq1d 7356	. . . . . . . 8 ⊢ (𝑥 = 𝐴 → ((𝑥↑𝑛) − 1) = ((𝐴↑𝑛) − 1))
22	21	breq2d 5101	. . . . . . 7 ⊢ (𝑥 = 𝐴 → (𝑁 ∥ ((𝑥↑𝑛) − 1) ↔ 𝑁 ∥ ((𝐴↑𝑛) − 1)))
23	22	rabbidv 3400	. . . . . 6 ⊢ (𝑥 = 𝐴 → {𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)} = {𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝐴↑𝑛) − 1)})
24	23	infeq1d 9357	. . . . 5 ⊢ (𝑥 = 𝐴 → inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < ) = inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝐴↑𝑛) − 1)}, ℝ, < ))
25		eqid 2730	. . . . 5 ⊢ (𝑥 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < )) = (𝑥 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < ))
26		ltso 11185	. . . . . 6 ⊢ < Or ℝ
27	26	infex 9374	. . . . 5 ⊢ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝐴↑𝑛) − 1)}, ℝ, < ) ∈ V
28	24, 25, 27	fvmpt 6924	. . . 4 ⊢ (𝐴 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} → ((𝑥 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < ))‘𝐴) = inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝐴↑𝑛) − 1)}, ℝ, < ))
29	19, 28	sylbir 235	. . 3 ⊢ ((𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → ((𝑥 ∈ {𝑛 ∈ ℤ ∣ (𝑛 gcd 𝑁) = 1} ↦ inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝑥↑𝑛) − 1)}, ℝ, < ))‘𝐴) = inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝐴↑𝑛) − 1)}, ℝ, < ))
30	16, 29	sylan9eq 2785	. 2 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1)) → ((odℤ‘𝑁)‘𝐴) = inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝐴↑𝑛) − 1)}, ℝ, < ))
31	30	3impb 1114	1 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → ((odℤ‘𝑁)‘𝐴) = inf({𝑛 ∈ ℕ ∣ 𝑁 ∥ ((𝐴↑𝑛) − 1)}, ℝ, < ))

Syntax hints:   → wi 4   ∧ wa 395   ∧ w3a 1086   = wceq 1541   ∈ wcel 2110  {crab 3393   class class class wbr 5089   ↦ cmpt 5170  ‘cfv 6477  (class class class)co 7341  infcinf 9320  ℝcr 10997  1c1 10999   < clt 11138   − cmin 11336  ℕcn 12117  ℤcz 12460  ↑cexp 13960   ∥ cdvds 16155   gcd cgcd 16397  od_ℤcodz 16666

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1968  ax-7 2009  ax-8 2112  ax-9 2120  ax-10 2143  ax-11 2159  ax-12 2179  ax-ext 2702  ax-rep 5215  ax-sep 5232  ax-nul 5242  ax-pow 5301  ax-pr 5368  ax-un 7663  ax-cnex 11054  ax-resscn 11055  ax-pre-lttri 11072  ax-pre-lttrn 11073

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1544  df-fal 1554  df-ex 1781  df-nf 1785  df-sb 2067  df-mo 2534  df-eu 2563  df-clab 2709  df-cleq 2722  df-clel 2804  df-nfc 2879  df-ne 2927  df-nel 3031  df-ral 3046  df-rex 3055  df-rmo 3344  df-reu 3345  df-rab 3394  df-v 3436  df-sbc 3740  df-csb 3849  df-dif 3903  df-un 3905  df-in 3907  df-ss 3917  df-nul 4282  df-if 4474  df-pw 4550  df-sn 4575  df-pr 4577  df-op 4581  df-uni 4858  df-iun 4941  df-br 5090  df-opab 5152  df-mpt 5171  df-id 5509  df-po 5522  df-so 5523  df-xp 5620  df-rel 5621  df-cnv 5622  df-co 5623  df-dm 5624  df-rn 5625  df-res 5626  df-ima 5627  df-iota 6433  df-fun 6479  df-fn 6480  df-f 6481  df-f1 6482  df-fo 6483  df-f1o 6484  df-fv 6485  df-ov 7344  df-er 8617  df-en 8865  df-dom 8866  df-sdom 8867  df-sup 9321  df-inf 9322  df-pnf 11140  df-mnf 11141  df-ltxr 11143  df-neg 11339  df-z 12461  df-odz 16668

This theorem is referenced by:  odzcllem  16696  odzdvds  16699  hashscontpow1  42133