Metamath Proof Explorer


Theorem fmtnofac1

Description: Divisor of Fermat number (Euler's Result), see ProofWiki "Divisor of Fermat Number/Euler's Result", 24-Jul-2021, https://proofwiki.org/wiki/Divisor_of_Fermat_Number/Euler's_Result ): "Let F_n be a Fermat number. Let m be divisor of F_n. Then m is in the form: k*2^(n+1)+1 where k is a positive integer." Here, however, k must be a nonnegative integer, because k must be 0 to represent 1 (which is a divisor of F_n ).

Historical Note: In 1747, Leonhard Paul Euler proved that a divisor of a Fermat number F_n is always in the form kx2^(n+1)+1. This was later refined to k*2^(n+2)+1 by François Édouard Anatole Lucas, see fmtnofac2 . (Contributed by AV, 30-Jul-2021)

Ref Expression
Assertion fmtnofac1 ( ( 𝑁 ∈ ℕ ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) )

Proof

Step Hyp Ref Expression
1 elnn1uz2 ( 𝑁 ∈ ℕ ↔ ( 𝑁 = 1 ∨ 𝑁 ∈ ( ℤ ‘ 2 ) ) )
2 5prm 5 ∈ ℙ
3 dvdsprime ( ( 5 ∈ ℙ ∧ 𝑀 ∈ ℕ ) → ( 𝑀 ∥ 5 ↔ ( 𝑀 = 5 ∨ 𝑀 = 1 ) ) )
4 2 3 mpan ( 𝑀 ∈ ℕ → ( 𝑀 ∥ 5 ↔ ( 𝑀 = 5 ∨ 𝑀 = 1 ) ) )
5 1nn0 1 ∈ ℕ0
6 5 a1i ( 𝑀 = 5 → 1 ∈ ℕ0 )
7 simpl ( ( 𝑀 = 5 ∧ 𝑘 = 1 ) → 𝑀 = 5 )
8 oveq1 ( 𝑘 = 1 → ( 𝑘 · 4 ) = ( 1 · 4 ) )
9 8 oveq1d ( 𝑘 = 1 → ( ( 𝑘 · 4 ) + 1 ) = ( ( 1 · 4 ) + 1 ) )
10 9 adantl ( ( 𝑀 = 5 ∧ 𝑘 = 1 ) → ( ( 𝑘 · 4 ) + 1 ) = ( ( 1 · 4 ) + 1 ) )
11 7 10 eqeq12d ( ( 𝑀 = 5 ∧ 𝑘 = 1 ) → ( 𝑀 = ( ( 𝑘 · 4 ) + 1 ) ↔ 5 = ( ( 1 · 4 ) + 1 ) ) )
12 df-5 5 = ( 4 + 1 )
13 4cn 4 ∈ ℂ
14 13 mulid2i ( 1 · 4 ) = 4
15 14 eqcomi 4 = ( 1 · 4 )
16 15 oveq1i ( 4 + 1 ) = ( ( 1 · 4 ) + 1 )
17 12 16 eqtri 5 = ( ( 1 · 4 ) + 1 )
18 17 a1i ( 𝑀 = 5 → 5 = ( ( 1 · 4 ) + 1 ) )
19 6 11 18 rspcedvd ( 𝑀 = 5 → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · 4 ) + 1 ) )
20 0nn0 0 ∈ ℕ0
21 20 a1i ( 𝑀 = 1 → 0 ∈ ℕ0 )
22 simpl ( ( 𝑀 = 1 ∧ 𝑘 = 0 ) → 𝑀 = 1 )
23 oveq1 ( 𝑘 = 0 → ( 𝑘 · 4 ) = ( 0 · 4 ) )
24 23 oveq1d ( 𝑘 = 0 → ( ( 𝑘 · 4 ) + 1 ) = ( ( 0 · 4 ) + 1 ) )
25 24 adantl ( ( 𝑀 = 1 ∧ 𝑘 = 0 ) → ( ( 𝑘 · 4 ) + 1 ) = ( ( 0 · 4 ) + 1 ) )
26 22 25 eqeq12d ( ( 𝑀 = 1 ∧ 𝑘 = 0 ) → ( 𝑀 = ( ( 𝑘 · 4 ) + 1 ) ↔ 1 = ( ( 0 · 4 ) + 1 ) ) )
27 13 mul02i ( 0 · 4 ) = 0
28 27 oveq1i ( ( 0 · 4 ) + 1 ) = ( 0 + 1 )
29 0p1e1 ( 0 + 1 ) = 1
30 28 29 eqtri ( ( 0 · 4 ) + 1 ) = 1
31 30 eqcomi 1 = ( ( 0 · 4 ) + 1 )
32 31 a1i ( 𝑀 = 1 → 1 = ( ( 0 · 4 ) + 1 ) )
33 21 26 32 rspcedvd ( 𝑀 = 1 → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · 4 ) + 1 ) )
34 19 33 jaoi ( ( 𝑀 = 5 ∨ 𝑀 = 1 ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · 4 ) + 1 ) )
35 4 34 syl6bi ( 𝑀 ∈ ℕ → ( 𝑀 ∥ 5 → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · 4 ) + 1 ) ) )
36 fveq2 ( 𝑁 = 1 → ( FermatNo ‘ 𝑁 ) = ( FermatNo ‘ 1 ) )
37 fmtno1 ( FermatNo ‘ 1 ) = 5
38 36 37 eqtrdi ( 𝑁 = 1 → ( FermatNo ‘ 𝑁 ) = 5 )
39 38 breq2d ( 𝑁 = 1 → ( 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ↔ 𝑀 ∥ 5 ) )
40 oveq1 ( 𝑁 = 1 → ( 𝑁 + 1 ) = ( 1 + 1 ) )
41 1p1e2 ( 1 + 1 ) = 2
42 40 41 eqtrdi ( 𝑁 = 1 → ( 𝑁 + 1 ) = 2 )
43 42 oveq2d ( 𝑁 = 1 → ( 2 ↑ ( 𝑁 + 1 ) ) = ( 2 ↑ 2 ) )
44 sq2 ( 2 ↑ 2 ) = 4
45 43 44 eqtrdi ( 𝑁 = 1 → ( 2 ↑ ( 𝑁 + 1 ) ) = 4 )
46 45 oveq2d ( 𝑁 = 1 → ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) = ( 𝑘 · 4 ) )
47 46 oveq1d ( 𝑁 = 1 → ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) = ( ( 𝑘 · 4 ) + 1 ) )
48 47 eqeq2d ( 𝑁 = 1 → ( 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ↔ 𝑀 = ( ( 𝑘 · 4 ) + 1 ) ) )
49 48 rexbidv ( 𝑁 = 1 → ( ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ↔ ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · 4 ) + 1 ) ) )
50 39 49 imbi12d ( 𝑁 = 1 → ( ( 𝑀 ∥ ( FermatNo ‘ 𝑁 ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ) ↔ ( 𝑀 ∥ 5 → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · 4 ) + 1 ) ) ) )
51 35 50 syl5ibr ( 𝑁 = 1 → ( 𝑀 ∈ ℕ → ( 𝑀 ∥ ( FermatNo ‘ 𝑁 ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ) ) )
52 fmtnofac2 ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) → ∃ 𝑛 ∈ ℕ0 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) )
53 id ( 𝑛 ∈ ℕ0𝑛 ∈ ℕ0 )
54 2nn0 2 ∈ ℕ0
55 54 a1i ( 𝑛 ∈ ℕ0 → 2 ∈ ℕ0 )
56 53 55 nn0mulcld ( 𝑛 ∈ ℕ0 → ( 𝑛 · 2 ) ∈ ℕ0 )
57 56 adantl ( ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) ∧ 𝑛 ∈ ℕ0 ) → ( 𝑛 · 2 ) ∈ ℕ0 )
58 57 adantr ( ( ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) ∧ 𝑛 ∈ ℕ0 ) ∧ 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) ) → ( 𝑛 · 2 ) ∈ ℕ0 )
59 simpr ( ( ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) ∧ 𝑛 ∈ ℕ0 ) ∧ 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) ) → 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) )
60 oveq1 ( 𝑘 = ( 𝑛 · 2 ) → ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) = ( ( 𝑛 · 2 ) · ( 2 ↑ ( 𝑁 + 1 ) ) ) )
61 60 oveq1d ( 𝑘 = ( 𝑛 · 2 ) → ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) = ( ( ( 𝑛 · 2 ) · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) )
62 59 61 eqeqan12d ( ( ( ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) ∧ 𝑛 ∈ ℕ0 ) ∧ 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) ) ∧ 𝑘 = ( 𝑛 · 2 ) ) → ( 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ↔ ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) = ( ( ( 𝑛 · 2 ) · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ) )
63 eluzge2nn0 ( 𝑁 ∈ ( ℤ ‘ 2 ) → 𝑁 ∈ ℕ0 )
64 63 nn0cnd ( 𝑁 ∈ ( ℤ ‘ 2 ) → 𝑁 ∈ ℂ )
65 add1p1 ( 𝑁 ∈ ℂ → ( ( 𝑁 + 1 ) + 1 ) = ( 𝑁 + 2 ) )
66 64 65 syl ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( ( 𝑁 + 1 ) + 1 ) = ( 𝑁 + 2 ) )
67 66 eqcomd ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( 𝑁 + 2 ) = ( ( 𝑁 + 1 ) + 1 ) )
68 67 oveq2d ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( 2 ↑ ( 𝑁 + 2 ) ) = ( 2 ↑ ( ( 𝑁 + 1 ) + 1 ) ) )
69 2cnd ( 𝑁 ∈ ( ℤ ‘ 2 ) → 2 ∈ ℂ )
70 peano2nn0 ( 𝑁 ∈ ℕ0 → ( 𝑁 + 1 ) ∈ ℕ0 )
71 63 70 syl ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( 𝑁 + 1 ) ∈ ℕ0 )
72 69 71 expp1d ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( 2 ↑ ( ( 𝑁 + 1 ) + 1 ) ) = ( ( 2 ↑ ( 𝑁 + 1 ) ) · 2 ) )
73 54 a1i ( 𝑁 ∈ ( ℤ ‘ 2 ) → 2 ∈ ℕ0 )
74 73 71 nn0expcld ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( 2 ↑ ( 𝑁 + 1 ) ) ∈ ℕ0 )
75 74 nn0cnd ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( 2 ↑ ( 𝑁 + 1 ) ) ∈ ℂ )
76 75 69 mulcomd ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( ( 2 ↑ ( 𝑁 + 1 ) ) · 2 ) = ( 2 · ( 2 ↑ ( 𝑁 + 1 ) ) ) )
77 68 72 76 3eqtrd ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( 2 ↑ ( 𝑁 + 2 ) ) = ( 2 · ( 2 ↑ ( 𝑁 + 1 ) ) ) )
78 77 adantr ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑛 ∈ ℕ0 ) → ( 2 ↑ ( 𝑁 + 2 ) ) = ( 2 · ( 2 ↑ ( 𝑁 + 1 ) ) ) )
79 78 oveq2d ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑛 ∈ ℕ0 ) → ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) = ( 𝑛 · ( 2 · ( 2 ↑ ( 𝑁 + 1 ) ) ) ) )
80 nn0cn ( 𝑛 ∈ ℕ0𝑛 ∈ ℂ )
81 80 adantl ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑛 ∈ ℕ0 ) → 𝑛 ∈ ℂ )
82 2cnd ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑛 ∈ ℕ0 ) → 2 ∈ ℂ )
83 75 adantr ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑛 ∈ ℕ0 ) → ( 2 ↑ ( 𝑁 + 1 ) ) ∈ ℂ )
84 81 82 83 mulassd ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑛 ∈ ℕ0 ) → ( ( 𝑛 · 2 ) · ( 2 ↑ ( 𝑁 + 1 ) ) ) = ( 𝑛 · ( 2 · ( 2 ↑ ( 𝑁 + 1 ) ) ) ) )
85 79 84 eqtr4d ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑛 ∈ ℕ0 ) → ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) = ( ( 𝑛 · 2 ) · ( 2 ↑ ( 𝑁 + 1 ) ) ) )
86 85 3ad2antl1 ( ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) ∧ 𝑛 ∈ ℕ0 ) → ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) = ( ( 𝑛 · 2 ) · ( 2 ↑ ( 𝑁 + 1 ) ) ) )
87 86 adantr ( ( ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) ∧ 𝑛 ∈ ℕ0 ) ∧ 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) ) → ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) = ( ( 𝑛 · 2 ) · ( 2 ↑ ( 𝑁 + 1 ) ) ) )
88 87 oveq1d ( ( ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) ∧ 𝑛 ∈ ℕ0 ) ∧ 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) ) → ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) = ( ( ( 𝑛 · 2 ) · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) )
89 58 62 88 rspcedvd ( ( ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) ∧ 𝑛 ∈ ℕ0 ) ∧ 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) )
90 89 rexlimdva2 ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) → ( ∃ 𝑛 ∈ ℕ0 𝑀 = ( ( 𝑛 · ( 2 ↑ ( 𝑁 + 2 ) ) ) + 1 ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ) )
91 52 90 mpd ( ( 𝑁 ∈ ( ℤ ‘ 2 ) ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) )
92 91 3exp ( 𝑁 ∈ ( ℤ ‘ 2 ) → ( 𝑀 ∈ ℕ → ( 𝑀 ∥ ( FermatNo ‘ 𝑁 ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ) ) )
93 51 92 jaoi ( ( 𝑁 = 1 ∨ 𝑁 ∈ ( ℤ ‘ 2 ) ) → ( 𝑀 ∈ ℕ → ( 𝑀 ∥ ( FermatNo ‘ 𝑁 ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ) ) )
94 1 93 sylbi ( 𝑁 ∈ ℕ → ( 𝑀 ∈ ℕ → ( 𝑀 ∥ ( FermatNo ‘ 𝑁 ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) ) ) )
95 94 3imp ( ( 𝑁 ∈ ℕ ∧ 𝑀 ∈ ℕ ∧ 𝑀 ∥ ( FermatNo ‘ 𝑁 ) ) → ∃ 𝑘 ∈ ℕ0 𝑀 = ( ( 𝑘 · ( 2 ↑ ( 𝑁 + 1 ) ) ) + 1 ) )