Metamath Proof Explorer

Theorem issqf

Description: Two ways to say that a number is squarefree. (Contributed by Mario Carneiro, 3-Oct-2014)

Ref Expression
Assertion issqf 
|- ( A e. NN -> ( ( mmu ` A ) =/= 0 <-> A. p e. Prime ( p pCnt A ) <_ 1 ) )

Proof

Step Hyp Ref Expression
1 isnsqf 
 |-  ( A e. NN -> ( ( mmu ` A ) = 0 <-> E. p e. Prime ( p ^ 2 ) || A ) )
2 1 necon3abid 
 |-  ( A e. NN -> ( ( mmu ` A ) =/= 0 <-> -. E. p e. Prime ( p ^ 2 ) || A ) )
3 ralnex 
 |-  ( A. p e. Prime -. ( p ^ 2 ) || A <-> -. E. p e. Prime ( p ^ 2 ) || A )
4 1nn0 
 |-  1 e. NN0
5 pccl 
 |-  ( ( p e. Prime /\ A e. NN ) -> ( p pCnt A ) e. NN0 )
6 5 ancoms 
 |-  ( ( A e. NN /\ p e. Prime ) -> ( p pCnt A ) e. NN0 )
7 nn0ltp1le 
 |-  ( ( 1 e. NN0 /\ ( p pCnt A ) e. NN0 ) -> ( 1 < ( p pCnt A ) <-> ( 1 + 1 ) <_ ( p pCnt A ) ) )
8 4 6 7 sylancr 
 |-  ( ( A e. NN /\ p e. Prime ) -> ( 1 < ( p pCnt A ) <-> ( 1 + 1 ) <_ ( p pCnt A ) ) )
9 1re 
 |-  1 e. RR
10 6 nn0red 
 |-  ( ( A e. NN /\ p e. Prime ) -> ( p pCnt A ) e. RR )
11 ltnle 
 |-  ( ( 1 e. RR /\ ( p pCnt A ) e. RR ) -> ( 1 < ( p pCnt A ) <-> -. ( p pCnt A ) <_ 1 ) )
12 9 10 11 sylancr 
 |-  ( ( A e. NN /\ p e. Prime ) -> ( 1 < ( p pCnt A ) <-> -. ( p pCnt A ) <_ 1 ) )
13 df-2 
 |-  2 = ( 1 + 1 )
14 13 breq1i 
 |-  ( 2 <_ ( p pCnt A ) <-> ( 1 + 1 ) <_ ( p pCnt A ) )
15 id 
 |-  ( p e. Prime -> p e. Prime )
16 nnz 
 |-  ( A e. NN -> A e. ZZ )
17 2nn0 
 |-  2 e. NN0
18 pcdvdsb 
 |-  ( ( p e. Prime /\ A e. ZZ /\ 2 e. NN0 ) -> ( 2 <_ ( p pCnt A ) <-> ( p ^ 2 ) || A ) )
19 17 18 mp3an3 
 |-  ( ( p e. Prime /\ A e. ZZ ) -> ( 2 <_ ( p pCnt A ) <-> ( p ^ 2 ) || A ) )
20 15 16 19 syl2anr 
 |-  ( ( A e. NN /\ p e. Prime ) -> ( 2 <_ ( p pCnt A ) <-> ( p ^ 2 ) || A ) )
21 14 20 bitr3id 
 |-  ( ( A e. NN /\ p e. Prime ) -> ( ( 1 + 1 ) <_ ( p pCnt A ) <-> ( p ^ 2 ) || A ) )
22 8 12 21 3bitr3d 
 |-  ( ( A e. NN /\ p e. Prime ) -> ( -. ( p pCnt A ) <_ 1 <-> ( p ^ 2 ) || A ) )
23 22 con1bid 
 |-  ( ( A e. NN /\ p e. Prime ) -> ( -. ( p ^ 2 ) || A <-> ( p pCnt A ) <_ 1 ) )
24 23 ralbidva 
 |-  ( A e. NN -> ( A. p e. Prime -. ( p ^ 2 ) || A <-> A. p e. Prime ( p pCnt A ) <_ 1 ) )
25 3 24 bitr3id 
 |-  ( A e. NN -> ( -. E. p e. Prime ( p ^ 2 ) || A <-> A. p e. Prime ( p pCnt A ) <_ 1 ) )
26 2 25 bitrd 
 |-  ( A e. NN -> ( ( mmu ` A ) =/= 0 <-> A. p e. Prime ( p pCnt A ) <_ 1 ) )