THE GARDEN

Recovering an Unknown Modulus via GCD (Successive Powers)

Updated 13 Sep 2026

• •

  What it is

  • •

    A technique for recovering an unknown prime modulus $p$ from a sequence of consecutive powers $a_n \equiv a_0 \cdot x^n \pmod p$ of an unknown base $x$, given only the sequence values (neither $p$ nor $x$ stated). Consecutive terms satisfy the ratio identity $a_{n+1}/a_n \equiv a_{n+2}/a_{n+1} \pmod p$; cross-multiplying gives $a_{n+1}^2 - a_n a_{n+2} \equiv 0 \pmod p$ — an integer (computed over the plain integers, no modular arithmetic needed) that $p$ divides exactly. Computing this difference from two or more overlapping triples gives several integers that are all multiples of $p$; their GCD is generally $p$ itself (or a small multiple of it, resolved by stripping small factors and checking primality/bit-length).

• •

  When to apply

  • •

    You're given a sequence of integers described as "successive powers of x modulo a prime p", with neither p nor x stated.

• •

  Math

  • •

    $a_{n+1}^2 - a_n a_{n+2} \equiv 0 \pmod p$ for every valid $n$, since all three terms share the common ratio $x$. Once $p$ is known, $x \equiv a_{n+1} \cdot a_n^{-1} \pmod p$ for any $n$.

• •

  Worked example

  • •

    Sequence [588,665,216,113,642,4,836,114,851,492,819,237]. Taking $(642,4,836)$ and $(4,836,114)$: $D_1 = 836^2 - 4 \cdot 114 = 698{,}440$, $D_2 = 4^2 - 642 \cdot 836 = -536{,}696$. $\gcd(D_1,D_2) = 7{,}352 = 8 \times 919$, and 919 is the three-digit prime the challenge asked for. Then $x \equiv 836 \cdot 4^{-1} \equiv 209 \pmod{919}$ — and this $(p,x)$ pair reproduces the entire 12-term sequence exactly as $a_n = a_0 \cdot x^n \bmod p$, confirmed by direct check.

• •

  Python

  • •

    from math import gcd
    D1 = seq[i+1]**2 - seq[i]*seq[i+2]
    D2 = seq[j+1]**2 - seq[j]*seq[j+2]
    p_candidate = gcd(D1, D2)
    # p_candidate may be p times a small integer factor -- strip small factors
    # and check primality / expected bit-length to isolate p itself
    x = (seq[i+1] * pow(seq[i], -1, p)) % p
    

• •

  Related

  • •

    Extended Euclidean Algorithm

• •

  Cards

  • •

    What identity lets you compute an integer multiple of the unknown modulus from three consecutive sequence terms?

    • •

      $a_{n+1}^2 - a_n \cdot a_{n+2} \equiv 0 \pmod p$, computed as a plain integer (not reduced) that p divides exactly.

  • •

    Why do you need at least two different triples from the sequence, not just one?

    • •

      A single difference could be a large multiple of p; taking the GCD of two (or more) such differences strips out the extraneous factors and isolates p itself.

◌ Explore connections in Graph view