Return to Revisions

We can reduce your problem to solving a linear equation modulo an integer. That way we can avoid functions like Minimize.

If a primitive root exists for the modulus, we can take discrete logarithms of both sides and easily solve for r. This following code finds the smallest positive r such that (base^r - const)/mod ∈ Integers.

HasPrimitiveRootQ[n_Integer?Positive] := 
  n < 8 || (OddQ[n] && PrimePowerQ[n]) || (OddQ[n/2] && PrimePowerQ[n/2])
HasPrimitiveRootQ[_] = False;

MinExponent[base_, const_, mod_?HasPrimitiveRootQ] := Module[{g,dlhs,drhs,phi,gcd,r,sol},
    g = PrimitiveRoot[mod];
    dlhs = MultiplicativeOrder[g, mod, {base}];
    drhs = MultiplicativeOrder[g, mod, {const}];
    phi = EulerPhi[mod];
    gcd = GCD[dlhs, drhs, phi];

    {dlhs, drhs, phi} /= gcd;

    r = Symbol["r"];
    Print["Solving ", Mod[dlhs r, phi] == Mod[drhs, phi]];

    sol = Solve[Mod[dlhs r, phi] == Mod[drhs, phi] && 0 < r <= phi, r, Integers];
    If[sol =!= {},
        r == Min[r /. sol],
        False
    ]
]

And your example reduces to solving a linear equation mod 3:

MinExponent[10, 1, 37]

Solving Mod[2r, 3] == 0

r == 3