Mod

[Jay-qu]

The mod function is defined as the amount by which a number exceeds the

largest integer multiple of the divisor that is not greater than that number.

 

Ok I get that and can generally see how that works with +ve and -ve numbers. What I dont see however is how it works with fractions :confused:

 

I just did a question and I have drawn a complete blank!

 

somehow:

 

[math]\frac{1}{8} mod 5 = 2 [/math]

 

rep to the first answer, I have an exam tomoro :D

 

J

[Jay-qu]

Hmmm I just did the calc on excel and it gives back 1/8 as I expected it to..

 

I dont see how my proffessor got this wrong..

[Jay-qu]

Ok I think I know where the answer came from, but Im not sure why..

 

so, xmod5 = 1 has solutions x = 6,11,16...

 

so for the 1/8 the first integer solution is 2

 

it works im running with it but I wouldnt mind knowing why..

[Tormod]

Hah, I thought everybody knew how this works.

[CraigD]

[math]\frac{1}{8} mod 5 = 2 [/math]

Start with the identity [math]\frac{1}{n} \cdot n = 1[/math]. This identity applies not only to an unbounded set of numbers, but to a set of modular numbers.

 

[math](2 \cdot 8) \mbox{mod} 5 =1[/math], satisfying this identity.

 

The question is a bit unconventional, as 8 is not a number modulo 5. Note, however, that [math]8 \mbox{mod} 5 = 3[/math], and [math]\frac13 \mbox{mod} 5 = 2[/math], an identity that holds for all unbounded-to-modular number mappings. Also note that the question assumes that the solution must be an element of the set of positive integers modulo 5, a finite set. This isn’t an unusual convention, as such sets are finite, and thus very handy. If the question had allowed the solution to be an element of the infinite set of rational numbers modulo 5, it wouldn’t have been much of a question, as [math]\frac18[/math] is a solution.

 

To find [math]n = \frac{a}{b} \mbox{mod} c[/math], you need to find 2 integers [math]n[/math] and [math]m[/math] such that [math]b \cdot n = c \cdot m + a[/math]. One method for doing this other than trial and error – just count [math]b[/math] the number modulo [math]c[/math] until it is [math]a[/math] – in programmatic terms,

Let x = b, n= 1
Do while x mod c not= a
 Let x= x + b, n= n +1

 

You can calculate the multiplicative inverses [math]\frac1{n}[/math] of all elements of a set of integer modular numbers

1 -> 1

2 -> 3

3 -> 2

4 -> 4

 

See if you can find [math]\frac1{763} \mbox{mod} 1741[/math]. If you have a programmable calculator of some kind, it should be trivial to program. If you’re doing it by hand, and are not bizarrely patient, you’ll need to find a more sophisticated method ;)

 

Also, can you say anything special about the existence of a solution when [math]c[/math] is not a prime number?

[Jay-qu]

Right on, thanks heaps Craig :)

 

I have the solution to your little problem (used an excel spread sheet)

 

[math]\frac{1}{763}mod1741=664[/math]

 

;)