Metamath Proof Explorer


Theorem cshweqrep

Description: If cyclically shifting a word by L position results in the word itself, the symbol at any position is repeated at multiples of L (modulo the length of the word) positions in the word. (Contributed by AV, 13-May-2018) (Revised by AV, 7-Jun-2018) (Revised by AV, 1-Nov-2018)

Ref Expression
Assertion cshweqrep W Word V L W cyclShift L = W I 0 ..^ W j 0 W I = W I + j L mod W

Proof

Step Hyp Ref Expression
1 oveq1 x = 0 x L = 0 L
2 1 oveq2d x = 0 I + x L = I + 0 L
3 2 fvoveq1d x = 0 W I + x L mod W = W I + 0 L mod W
4 3 eqeq2d x = 0 W I = W I + x L mod W W I = W I + 0 L mod W
5 4 imbi2d x = 0 W Word V L W cyclShift L = W I 0 ..^ W W I = W I + x L mod W W Word V L W cyclShift L = W I 0 ..^ W W I = W I + 0 L mod W
6 oveq1 x = y x L = y L
7 6 oveq2d x = y I + x L = I + y L
8 7 fvoveq1d x = y W I + x L mod W = W I + y L mod W
9 8 eqeq2d x = y W I = W I + x L mod W W I = W I + y L mod W
10 9 imbi2d x = y W Word V L W cyclShift L = W I 0 ..^ W W I = W I + x L mod W W Word V L W cyclShift L = W I 0 ..^ W W I = W I + y L mod W
11 oveq1 x = y + 1 x L = y + 1 L
12 11 oveq2d x = y + 1 I + x L = I + y + 1 L
13 12 fvoveq1d x = y + 1 W I + x L mod W = W I + y + 1 L mod W
14 13 eqeq2d x = y + 1 W I = W I + x L mod W W I = W I + y + 1 L mod W
15 14 imbi2d x = y + 1 W Word V L W cyclShift L = W I 0 ..^ W W I = W I + x L mod W W Word V L W cyclShift L = W I 0 ..^ W W I = W I + y + 1 L mod W
16 oveq1 x = j x L = j L
17 16 oveq2d x = j I + x L = I + j L
18 17 fvoveq1d x = j W I + x L mod W = W I + j L mod W
19 18 eqeq2d x = j W I = W I + x L mod W W I = W I + j L mod W
20 19 imbi2d x = j W Word V L W cyclShift L = W I 0 ..^ W W I = W I + x L mod W W Word V L W cyclShift L = W I 0 ..^ W W I = W I + j L mod W
21 zcn L L
22 21 mul02d L 0 L = 0
23 22 adantl W Word V L 0 L = 0
24 23 adantr W Word V L W cyclShift L = W I 0 ..^ W 0 L = 0
25 24 oveq2d W Word V L W cyclShift L = W I 0 ..^ W I + 0 L = I + 0
26 elfzoelz I 0 ..^ W I
27 26 zcnd I 0 ..^ W I
28 27 addid1d I 0 ..^ W I + 0 = I
29 28 ad2antll W Word V L W cyclShift L = W I 0 ..^ W I + 0 = I
30 25 29 eqtrd W Word V L W cyclShift L = W I 0 ..^ W I + 0 L = I
31 30 oveq1d W Word V L W cyclShift L = W I 0 ..^ W I + 0 L mod W = I mod W
32 zmodidfzoimp I 0 ..^ W I mod W = I
33 32 ad2antll W Word V L W cyclShift L = W I 0 ..^ W I mod W = I
34 31 33 eqtr2d W Word V L W cyclShift L = W I 0 ..^ W I = I + 0 L mod W
35 34 fveq2d W Word V L W cyclShift L = W I 0 ..^ W W I = W I + 0 L mod W
36 fveq1 W = W cyclShift L W I + y L mod W = W cyclShift L I + y L mod W
37 36 eqcoms W cyclShift L = W W I + y L mod W = W cyclShift L I + y L mod W
38 37 ad2antrl W Word V L W cyclShift L = W I 0 ..^ W W I + y L mod W = W cyclShift L I + y L mod W
39 38 adantl y 0 W Word V L W cyclShift L = W I 0 ..^ W W I + y L mod W = W cyclShift L I + y L mod W
40 simprll y 0 W Word V L W cyclShift L = W I 0 ..^ W W Word V
41 simprlr y 0 W Word V L W cyclShift L = W I 0 ..^ W L
42 elfzo0 I 0 ..^ W I 0 W I < W
43 nn0z I 0 I
44 43 adantr I 0 W I
45 nn0z y 0 y
46 zmulcl y L y L
47 45 46 sylan y 0 L y L
48 47 ancoms L y 0 y L
49 zaddcl I y L I + y L
50 44 48 49 syl2an I 0 W L y 0 I + y L
51 simplr I 0 W L y 0 W
52 50 51 jca I 0 W L y 0 I + y L W
53 52 ex I 0 W L y 0 I + y L W
54 53 3adant3 I 0 W I < W L y 0 I + y L W
55 42 54 sylbi I 0 ..^ W L y 0 I + y L W
56 55 adantl W cyclShift L = W I 0 ..^ W L y 0 I + y L W
57 56 expd W cyclShift L = W I 0 ..^ W L y 0 I + y L W
58 57 com12 L W cyclShift L = W I 0 ..^ W y 0 I + y L W
59 58 adantl W Word V L W cyclShift L = W I 0 ..^ W y 0 I + y L W
60 59 imp W Word V L W cyclShift L = W I 0 ..^ W y 0 I + y L W
61 60 impcom y 0 W Word V L W cyclShift L = W I 0 ..^ W I + y L W
62 zmodfzo I + y L W I + y L mod W 0 ..^ W
63 61 62 syl y 0 W Word V L W cyclShift L = W I 0 ..^ W I + y L mod W 0 ..^ W
64 cshwidxmod W Word V L I + y L mod W 0 ..^ W W cyclShift L I + y L mod W = W I + y L mod W + L mod W
65 40 41 63 64 syl3anc y 0 W Word V L W cyclShift L = W I 0 ..^ W W cyclShift L I + y L mod W = W I + y L mod W + L mod W
66 nn0re I 0 I
67 zre L L
68 nn0re y 0 y
69 nnrp W W +
70 remulcl y L y L
71 70 ancoms L y y L
72 readdcl I y L I + y L
73 71 72 sylan2 I L y I + y L
74 73 ancoms L y I I + y L
75 74 adantl W + L y I I + y L
76 simprll W + L y I L
77 simpl W + L y I W +
78 modaddmod I + y L L W + I + y L mod W + L mod W = I + y L + L mod W
79 75 76 77 78 syl3anc W + L y I I + y L mod W + L mod W = I + y L + L mod W
80 recn I I
81 80 adantl L y I I
82 70 recnd y L y L
83 82 ancoms L y y L
84 83 adantr L y I y L
85 recn L L
86 85 adantr L y L
87 86 adantr L y I L
88 81 84 87 addassd L y I I + y L + L = I + y L + L
89 recn y y
90 89 adantl L y y
91 1cnd L y 1
92 90 91 86 adddird L y y + 1 L = y L + 1 L
93 85 mulid2d L 1 L = L
94 93 adantr L y 1 L = L
95 94 oveq2d L y y L + 1 L = y L + L
96 92 95 eqtr2d L y y L + L = y + 1 L
97 96 adantr L y I y L + L = y + 1 L
98 97 oveq2d L y I I + y L + L = I + y + 1 L
99 88 98 eqtrd L y I I + y L + L = I + y + 1 L
100 99 adantl W + L y I I + y L + L = I + y + 1 L
101 100 oveq1d W + L y I I + y L + L mod W = I + y + 1 L mod W
102 79 101 eqtrd W + L y I I + y L mod W + L mod W = I + y + 1 L mod W
103 102 ex W + L y I I + y L mod W + L mod W = I + y + 1 L mod W
104 69 103 syl W L y I I + y L mod W + L mod W = I + y + 1 L mod W
105 104 expd W L y I I + y L mod W + L mod W = I + y + 1 L mod W
106 105 com12 L y W I I + y L mod W + L mod W = I + y + 1 L mod W
107 67 68 106 syl2an L y 0 W I I + y L mod W + L mod W = I + y + 1 L mod W
108 107 com13 I W L y 0 I + y L mod W + L mod W = I + y + 1 L mod W
109 66 108 syl I 0 W L y 0 I + y L mod W + L mod W = I + y + 1 L mod W
110 109 imp I 0 W L y 0 I + y L mod W + L mod W = I + y + 1 L mod W
111 110 3adant3 I 0 W I < W L y 0 I + y L mod W + L mod W = I + y + 1 L mod W
112 42 111 sylbi I 0 ..^ W L y 0 I + y L mod W + L mod W = I + y + 1 L mod W
113 112 expd I 0 ..^ W L y 0 I + y L mod W + L mod W = I + y + 1 L mod W
114 113 adantld I 0 ..^ W W Word V L y 0 I + y L mod W + L mod W = I + y + 1 L mod W
115 114 adantl W cyclShift L = W I 0 ..^ W W Word V L y 0 I + y L mod W + L mod W = I + y + 1 L mod W
116 115 impcom W Word V L W cyclShift L = W I 0 ..^ W y 0 I + y L mod W + L mod W = I + y + 1 L mod W
117 116 impcom y 0 W Word V L W cyclShift L = W I 0 ..^ W I + y L mod W + L mod W = I + y + 1 L mod W
118 117 fveq2d y 0 W Word V L W cyclShift L = W I 0 ..^ W W I + y L mod W + L mod W = W I + y + 1 L mod W
119 39 65 118 3eqtrd y 0 W Word V L W cyclShift L = W I 0 ..^ W W I + y L mod W = W I + y + 1 L mod W
120 119 eqeq2d y 0 W Word V L W cyclShift L = W I 0 ..^ W W I = W I + y L mod W W I = W I + y + 1 L mod W
121 120 biimpd y 0 W Word V L W cyclShift L = W I 0 ..^ W W I = W I + y L mod W W I = W I + y + 1 L mod W
122 121 ex y 0 W Word V L W cyclShift L = W I 0 ..^ W W I = W I + y L mod W W I = W I + y + 1 L mod W
123 122 a2d y 0 W Word V L W cyclShift L = W I 0 ..^ W W I = W I + y L mod W W Word V L W cyclShift L = W I 0 ..^ W W I = W I + y + 1 L mod W
124 5 10 15 20 35 123 nn0ind j 0 W Word V L W cyclShift L = W I 0 ..^ W W I = W I + j L mod W
125 124 com12 W Word V L W cyclShift L = W I 0 ..^ W j 0 W I = W I + j L mod W
126 125 ralrimiv W Word V L W cyclShift L = W I 0 ..^ W j 0 W I = W I + j L mod W
127 126 ex W Word V L W cyclShift L = W I 0 ..^ W j 0 W I = W I + j L mod W