Solución:
La afirmación general es que siempre que tengamos una raíz cuadrada no trivial de $ 1 $ módulo $ n $, un valor $ c $ tal que $$ c ^ 2 equiv 1 pmod {n}, qquad c not equiv pm1 pmod {n}, $$ entonces obtenemos una factorización de $ n $.
Si $ c ^ 2 equiv 1 pmod n $, entonces $ (c + 1) (c-1) equiv 0 pmod n $.
Si $ c + 1 $ fueran primos relativos a $ n $, entonces tendría un módulo inverso $ n $, y podríamos multiplicar por $ (c + 1) ^ {- 1} $ para concluir que $ c-1 equiv 0 pmod n $. Pero esto se descarta por nuestra suposición de que $ c not equiv 1 pmod n $.
Si $ c + 1 $ fueran divisibles por $ n $, entonces tendríamos $ c + 1 equiv 0 pmod n $. Pero esto se descarta por nuestra suposición de que $ c not equiv -1 pmod n $.
Entonces, la única posibilidad restante es que $ c + 1 $ comparta algunos factores primos, pero no todos, con $ n $: que $ gcd (c + 1, n) $ es un factor no trivial de $ n $.
Lo mismo ocurre con el otro factor $ c-1 $.
De manera más general, siempre que encontramos $ a $ y $ b $ tales que $ a ^ 2 equiv b ^ 2 pmod n $ pero $ a no equiv pm b pmod n $, el mismo argumento muestra que $ gcd (a + b, n) $ y $ gcd (ab, n) $ son factores no triviales de $ n $. Esta es la base de muchos algoritmos de factorización de enteros que comienzan con el método de factorización de Fermat y terminan con el tamiz cuadrático.
Desde $ b ^ { frac {n-1} {2 ^ r}} equiv 1 pmod n $, vemos que existe un entero $ m $ tal que $$ b ^ { frac {n-1} {2 ^ r}} = mn + 1 tag1 $$ Desde $ b ^ { frac {n-1} {2 ^ {r + 1}}} not equiv pm 1 pmod n $, vemos que existen enteros $ k, r $ tales que $$ b ^ { frac {n-1} {2 ^ {r + 1}}} = kn + r + 1 tag2 $$ donde $$ text {$ 1 le r le n-1 quad $ con $ quad r not = n-2 $} tag3 $$
Como $ frac {n-1} {2 ^ r} $ es par, obtenemos, de $ (1) (2) $, $$ mn + 1 = b ^ { frac {n-1} {2 ^ r}} = b ^ { frac {n-1} {2 ^ {r + 1}} times 2} = left (b ^ { frac {n-1} {2 ^ {r + 1}} } right) ^ 2 = (kn + r + 1) ^ 2 = (k ^ 2n + 2kr + 2k) n + (r + 1) ^ 2 $$ lo que implica $$ 1 equiv (r + 1) ^ 2 equiv r ^ 2 + 2r + 1 pmod n $$ lo que implica $$ r (r + 2) equiv 0 pmod n tag4 $$
Aquí, suponiendo que $ r + 2 = n + 1 $ implica $ r equiv 0 pmod n $, lo cual es imposible.
Entonces, de $ (3) $, tenemos $ 1 lt r lt n $ y $ 1 lt r + 2 lt n $.
De estos y $ (4) $ se deduce que tanto $ r $ como $ r + 2 $ son divisores no triviales de $ n $.
Tenemos $ b ^ { frac {n-1} {2 ^ {r + 1}}} + 1 = kn + r + 2 $. Dado que $ r + 2 $ es un divisor no trivial de $ n $, vemos que $ gcd left (b ^ { frac {n-1} {2 ^ {r + 1}}} + 1, n right) $ es un divisor no trivial de $ n $.
Tenemos $ b ^ { frac {n-1} {2 ^ {r + 1}}} – 1 = kn + r $. Dado que $ r $ es un divisor no trivial de $ n $, vemos que $ gcd left (b ^ { frac {n-1} {2 ^ {r + 1}}} -1, n right ) $ es un divisor no trivial de $ n $.