CLRS中Miller-Rabin的WITNESS伪代码是否可简化？求反例验证

我正在研读*《算法导论》（CLRS，第3版）*第969页中Miller-Rabin素性测试的辅助函数WITNESS，原书给出的伪代码如下：

WITNESS(a, n)
    let t and u be such that t >= 1, u is odd, and n-1 = 2^t u
    x_0 = MODULAR-EXPONENTIATION(a, u, n)
    for i = 1 to t
        x_i = x_{i-1}^2 mod n
        if x_i == 1 and x_{i-1} != 1 and x_{i-1} != n-1
            return TRUE
    if x_t != 1
        return TRUE
    return FALSE

已知MODULAR-EXPONENTIATION的返回值范围是[0, n-1]，我个人认为上述伪代码完全等价于下面这个简化版本：

WITNESS(a, n)
    let t and u be such that t >= 1, u is odd, and n-1 = 2^t u
    x_0 = MODULAR-EXPONENTIATION(a, u, n)
    if x_0 == 1 or x_0 == n-1
        return FALSE
    else
        return TRUE

但这显然有问题——毕竟Miller-Rabin的核心逻辑应该依赖循环中的多次平方检查才对，所以我的等价推论肯定是错的。有没有简单的反例可以证明我的结论不成立？

内容的提问来源于stack exchange，提问作者xdavidliu