Message Boards Message Boards

0
|
4633 Views
|
4 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Modular computation and fractions?

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

POSTED BY: Mutatis Mutandis
4 Replies
Anonymous User
Anonymous User
Posted 8 years ago
Attachments:
POSTED BY: Anonymous User
Anonymous User
Anonymous User
Posted 8 years ago

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)

POSTED BY: Anonymous User

tnk's i try

POSTED BY: Mutatis Mutandis

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.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract