When studying modular arithmetic, we made the claim that, if we replace a variable in an arithmetic expression with a value that it is congruent to, the resulting expression will be congruent to the one we started with. We now have sufficient tools to prove that, and we will do so in this problem. We start by formalizing arithmetic expressions. Consider the set Expr representing parse trees for arithmetic expressions, defined recursively as follows: Bases Step: Variable(x) is in Expr representing the variable x, and for any v E Z, Number(v) is in Expr repre- senting the integer v. Recursive Step: For any s and t in Expr Plus(s, t) is in Expr representing s + t, and Times(s, t) is in Expr representing s - t. For example, the expression "3 + 4x" would become Plus(Number(3), Times(Number(4), Variable(x))). Every pos- sible arithmetic expression (with a single variable x) can be represented by an element of Expr If we choose a specific, integer value v E Z for the variable x, then we can calculate the value of the entire expression, with r = v, recursively, as follows: value, (Number(w)) = W VW EZ value, (Variable(r)) = value, (Plus(a, b)) = value,(a) + value.(b) Va, be Expr value, (Times(a, b)) = value,(a) . value,(b) Va, be Expr Now, we define the function subst, which substitutes the expression ce Expr for all instances of the variable r in an arithmetic expression, resulting in a new Expr as follows: subst (Number(w)) = Number(w) VW EZ substvariable(x)) = C subst (Plus(a, b)) = Plus(subst (a), subst (b)) Va, b E Expr subst (Times(a, b)) = Times(subst (a), subste(b)) Va, be ExprWith those definitions in place, we want to prove: Vu E Z ((value, (Variable(r)) = value,(c)(mod m)) -+ (Va E Expr (value,(a) = value, (subst.(a)) (mod m)) ) ), where m > 0 is an integer and c e Expr is a fixed arithmetic expression. In English, this says, for any value we might pick for x, if the value of the expression c is congruent to that of z, the value of any expression a that uses the variable x is congruent to the value of the same expression with c substituted for r. (Le., if we replace every instance of x in the expression a by c, we get an expression whose value is congruent to that of a.) For example, if c is the Expr for x + 3m, then the claim says that we can replace a by a + 3m in any Expr and the result will be an Expr whose value is congruent to the original one, modulo m, since & = r + 3m (mod m). For example, we could replace x by x + 3m in the Expr for 5(a + 7) to get the Expr for 5((x + 3m) + 7), which would simplify to 5r + 15m + 7. This second expression is not the same as the first, but their difference, 15m, disappears when we work modulo m. Prove the claim above using structural induction over a e Expr Hint: Our solution is shorter than the problem statement! This proof also is all "easy parts". It requires no deep insights. To prove it, just follow the structure of the claim we are trying to prove