Methods and apparatuses are described for formally verifying a bit-serial division circuit design or a bit-serial square-root circuit design. Some embodiments formally verify a bit-serial division circuit design using a set of properties that can be efficiently proven using a bit-level solver. In some embodiments, the set of properties that are used for verifying a bit-serial division circuit design does not include any terms that multiply a w-bit partial quotient with the divisor. Some embodiments formally verify a bit-serial square-root circuit design using a set of properties that can be efficiently proven using a bit-level solver. In some embodiments, the set of properties that are used for verifying a bit-serial square-root circuit design does not include any terms that compute a square of a w-bit partial square-root.