Modular computation and fractions?

Questions
,
1

Premise:

In modular computing each number relatively prime with the module M is a divisor of all numbers in the module range.

In Mod 90, there are 24 numbers, relatively prime with 90:

1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89

We note that couples are complementary to 90: 1 + 89 = 90, 7 + 83 = 90, …, 43 + 47 = 90

We can identify 12 pairs whose product a*b ? 1 mod 90:

Solve [{Mod [a * b, 90] == 1, 0 ? {a, b} ? 90}, {a, b}, Integers]

{a → 01, b → 01}, → 1*1 = 1 ? 1 Mod 90

{a → 07, b → 13}, → 7*13 = 91 ? 1 Mod 90

{a → 11, b → 41}, → 11*41 = 451 ? 1 Mod 90

{a → 13, b → 07}, → 13*7 = 91 ? 1 Mod 90

{a → 17, b → 53}, → 17*53 = 901 ? 1 Mod 90

{a → 19, b → 19}, → 19*19 = 361 ? 1 Mod 90

{a → 23, b → 47}, → 23*47 = 1081 ? 1 Mod 90

{a → 29, b → 59}, → 29*59 = 1711 ? 1 Mod 90

{a → 31, b → 61}, → 31*61 = 1891 ? 1 Mod 90

{a → 37, b → 73}, → 37*73 = 2701 ? 1 Mod 90

{a → 41, b → 11}, → 41*11 = 451 ? 1 Mod 90

{a → 43, b → 67}, → 43*67 = 2881 ? 1 Mod 90

{a → 47, b → 23}, → 47*23 = 1081 ? 1 Mod 90

{a → 49, b → 79}, → 49*79 = 3871 ? 1 Mod 90

{a → 53, b → 17}, → 53*17 = 901 ? 1 Mod 90

{a → 59, b → 29}, → 59*29 = 1711 ? 1 Mod 90

{a → 61, b → 31}, → 61*31 = 1891 ? 1 Mod 90

{a → 67, b → 43}, → 67*43 = 2881 ? 1 Mod 90

{a → 71, b → 71}, → 71*71 = 5041 ? 1 Mod 90

{a → 73, b → 37}, → 73*37 = 2701 ? 1 Mod 90

{a → 77, b → 83}, → 77*83 = 6391 ? 1 Mod 90

{a → 79, b → 49}, → 79*49 = 3871 ? 1 Mod 90

{a → 83, b → 77}, → 83*77 = 6391 ? 1 Mod 90

{a → 89, b → 89}, → 89*89 = 7921 ? 1 Mod 90

Then multiplying any number N * 1, 91, 451, 91, 901, 361, 1081, 1711, 1891, 2701, 451, 2881, 1081, 3871, 901, 1711, 1891, 2881, 5041, 2701, 6391, 3871, 6391, 7921 Mod 90 we get the same start number N.

The number obtained for example by: N * 91 = N Mod 90 = N * 7 * 13 which will be divisible both by 7 that from 13, then if you want to divide by 7 or by 13:

N / 7 = N * 7 * 13 / 7 = N * 13 Mod 90

N / 13 = N * 7 * 13 / 13 = N * 7 Mod 90

Question:

Now, if I get fractions as output, which in the modular calculation, as said above, can become integers …

{3/5, 2, 13, 19, 43/2, 295/11, 139/5, 41, 251/5, 53, 63, 191/3, 75, 997/13, 78, 82, 83, 259/3, 1145/13, 971/11, 443/5, 89}

295 / 11 = 295 * 41 = 35 mod 90

997 / 13 = 997 * 7 = 49 mod 90

1145 / 13 = 1145 * 7 = 5 mod 90

971 / 11 = 971 * 41 = 31 mod 90

If fraction is N/a how can I set a formula, based on the denominator a, that multiply the numerator N * b where a and b are a pair whose product ? 1 Mod 90? (Eg. 23/7 = 23*13 Mod 90)

thanks

2

This is a long post and I’m not sure I correctly understand the question being posed. Is it the modular inverse being sought? If so, maybe something like the code below will be useful.

In[282]:= PowerMod[Denominator[23/7], -1, 90]

(* Out[282]= 13 *)

Also there will be a ModularInverse function in a (probably not distant) future release.

3

tnk’s i try

4

I was just about to delete this comment, but want you to look at something.

i’m not sure either, i may check back in with a better answer

if i remember PowerMod[] doesnt’ support fractions. and it doesn’t need to. increasing fractions is just like increasing numeric width (has same effect on solving time)

You can likely multiply through before, and divide through after, and get the same answer is my guess.

(* you seem to know the above, upon my second reading *)

i investigated the question “can ChineseRemainder do fractions” which involves diophantine and “modular equations”. i made a function which gives a table of (simple) diophantine equations, ie table of solutions to
ax + by = 1, and another one that works using PowerMod for solutions specifically involving in solving a C.R.)

(the packge is called cr, and is at https://sourceforge.net/p/nchineseremainders/, its' a kiind notebook on parts of a discrete math book, and includes a new "better" way to solve cr - and a graphic overview how, it gets all multiples of solution - but i don’t think it will be helpful with your specific problem per say, you’d only view it for enlightenment on the issues and ways to solve cr`, of which your problem is one part)

5

here is the something. it shows solutions to a system of modular equations (chinese remainder problem)

when working with modular remember they are all “sloped” and your talking about finding the intersections of various rises (the graph is product by the package to show cr sol’n for euqations indicated by the input vectors)

i mention it because one can get lost in the world of identity rules and forget that these problems come down to simple geometric solutions (like gcd does)

enjoy

crchart3[Range[15], Prime@Range[15], 10, 50]