# 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?

## closed as off-topic by John Doty, bbgodfrey, m_goldberg, José Antonio Díaz Navas, SektorApr 6 '18 at 12:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question cannot be answered without additional information. Questions on problems in code must describe the specific problem and include valid code to reproduce it. Any data used for programming examples should be embedded in the question or code to generate the (fake) data must be included." – bbgodfrey, José Antonio Díaz Navas, Sektor
If this question can be reworded to fit the rules in the help center, please edit the question.

• 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] – user6014 Apr 6 '18 at 4:23

## 2 Answers

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

ex = {a -> #[],
b -> #[]} & /@ (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.