Revisions to Find the minimum integer r such that $(10^r - 1)/37$ is an integer

Takes away the call to Solve

Source Link

edited Dec 29, 2014 at 16:20

36.8k
1
94
143

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 (b^r - c)/mod ∈ Integers.

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

MinExponent[{b_, c_, mod_?HasPrimitiveRootQ}, r_] := Module[{g,dlhs,drhs,phi,gcd,sol},
    g = PrimitiveRoot[mod];
    dlhs = MultiplicativeOrder[g, mod, {b}];
    drhs = MultiplicativeOrder[g, mod, {c}];
    phi = EulerPhi[mod];
    gcd = GCD[dlhs, drhs, phi];

    {dlhs, drhs, phi} /= gcd;

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

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

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

MinExponent[{10, 1, 37}, r]

Solving Mod[2r, 3] == 0

r == 3

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 (b^r - c)/mod ∈ Integers.

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

MinExponent[{b_, c_, mod_?HasPrimitiveRootQ}, r_] := Module[{g,dlhs,drhs,phi,gcd,sol},
    g = PrimitiveRoot[mod];
    dlhs = MultiplicativeOrder[g, mod, {b}];
    drhs = MultiplicativeOrder[g, mod, {c}];
    phi = EulerPhi[mod];
    gcd = GCD[dlhs, drhs, phi];

    {dlhs, drhs, phi} /= gcd;

    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}, r]

Solving Mod[2r, 3] == 0

r == 3

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 (b^r - c)/mod ∈ Integers.

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

MinExponent[{b_, c_, mod_?HasPrimitiveRootQ}, r_] := Module[{g,dlhs,drhs,phi,gcd,sol},
    g = PrimitiveRoot[mod];
    dlhs = MultiplicativeOrder[g, mod, {b}];
    drhs = MultiplicativeOrder[g, mod, {c}];
    phi = EulerPhi[mod];
    gcd = GCD[dlhs, drhs, phi];

    {dlhs, drhs, phi} /= gcd;

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

    r == Mod[drhs*PowerMod[dlhs, -1, phi], phi, 1]
]

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

MinExponent[{10, 1, 37}, r]

Solving Mod[2r, 3] == 0

r == 3

Modifies syntax

Source Link

edited Dec 29, 2014 at 16:12

Greg Hurst

36.8k
1
94
143

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^rb^r - constc)/mod ∈ Integers.

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

MinExponent[base_MinExponent[{b_, const_c_, mod_?HasPrimitiveRootQ]HasPrimitiveRootQ}, r_] := Module[{g,dlhs,drhs,phi,gcd,r,sol},
    g = PrimitiveRoot[mod];
    dlhs = MultiplicativeOrder[g, mod, {baseb}];
    drhs = MultiplicativeOrder[g, mod, {constc}];
    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[10MinExponent[{10, 1, 37]37}, r]

Solving Mod[2r, 3] == 0

r == 3

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

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 (b^r - c)/mod ∈ Integers.

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

MinExponent[{b_, c_, mod_?HasPrimitiveRootQ}, r_] := Module[{g,dlhs,drhs,phi,gcd,sol},
    g = PrimitiveRoot[mod];
    dlhs = MultiplicativeOrder[g, mod, {b}];
    drhs = MultiplicativeOrder[g, mod, {c}];
    phi = EulerPhi[mod];
    gcd = GCD[dlhs, drhs, phi];

    {dlhs, drhs, phi} /= gcd;

    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}, r]

Solving Mod[2r, 3] == 0

r == 3

added 45 characters in body

Source Link

edited Dec 29, 2014 at 16:06

Greg Hurst

36.8k
1
94
143

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]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] == 0Solving Mod[2r, 3] == 0

r == 3

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]
    r == Min[r /. sol]
]

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

MinExponent[10, 1, 37]

Solving Mod[2r, 3] == 0

r == 3

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

Source Link

created Dec 29, 2014 at 15:25

Greg Hurst

36.8k
1
94
143

Loading

Stack Exchange Network

Return to Answer