0
$\begingroup$

I need to find $a$ and $b$ such that $a b = 1 \mod 4$? I do not know how to write the code. Could someone help me?

$\endgroup$
  • 1
    $\begingroup$ How about {a->1,b->1}? $\endgroup$ – John Doty Apr 5 '18 at 22:56
  • $\begingroup$ what do you mean? $\endgroup$ – ALBERT LI Apr 5 '18 at 23:01
  • $\begingroup$ It's an instance that solves your problem, as you stated it. $\endgroup$ – John Doty Apr 5 '18 at 23:09
  • 2
    $\begingroup$ FindInstance[Mod[a*b, 4] == 1, {a, b}, Integers, 4] $\endgroup$ – ktm Apr 6 '18 at 4:23
2
$\begingroup$

There are an infinite number of {a, b} pairs. Some examples,

ex = {a -> #[[1]], 
    b -> #[[2]]} & /@ (Select[Table[FactorInteger[4 n + 1], {n, 20}], 
     Length[#] == 2 &] /. {b_?NumericQ, e_?NumericQ} :> b^e)

(* {{a -> 3, b -> 7}, {a -> 3, b -> 11}, {a -> 9, b -> 5}, {a -> 3, 
  b -> 19}, {a -> 5, b -> 13}, {a -> 3, b -> 23}, {a -> 7, b -> 11}} *)

Verifying,

And @@ ((Mod[a b, 4] == 1) /. ex)

(* True *)

Or

ex2 = FindInstance[Mod[a b, 4] == 1 && a > 0 && b > 0, {a, b}, 
  Integers, 10]

(* {{a -> 3, b -> 327}, {a -> 2653, b -> 1}, {a -> 2553, 
  b -> 221}, {a -> 2095, b -> 3}, {a -> 2075, b -> 3}, {a -> 3023, 
  b -> 3}, {a -> 3947, b -> 3}, {a -> 3023, b -> 67}, {a -> 2527, 
  b -> 143}, {a -> 3299, b -> 3}} *)

And @@ ((Mod[a b, 4] == 1) /. ex2)

(* True *)
| improve this answer | |
$\endgroup$
2
$\begingroup$
b = PowerMod[a, -1, 4];

This is true for any integer a such that a modulo 4 is not 0.

This simply finds the modular multiplicative inverse of a modulo 4, using PowerMod.

| improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.