Code for finding $a$ and $b$ such that $a b = 1 \mod 4$ [closed]

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?

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

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 *)

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.