Discrete Algebraic Methods

2.6 (c) The encoding function is injective on the given domain: suppose there exist x, x ̃ ∈ 00{0, 1}400 with x > x̃ and x2 ≡ x̃2 mod 253. Then, (x − x̃)(x + x̃) ≡ 0 mod 253. Now, there are two cases. Either one of the two factors is 0 or one is a multiple of 11, and the other a multiple of 23.We have x − x ̃ ≠ 0 and x + x ̃ ≢ 0 mod 253 because x + x ̃ cannot exceed 120. Thus, the only remaining case is x − x ̃ being a multiple of 11 or 23. The numbers x and x ̃ are both multiples of 4. From we obtain that x − x ̃ can only be a multiple of 11, and has to hold. With this yields and In particular, x + x ̃ is not divisible by 23. This is a contradiction; ...