Menu
I'm stuck on this cryptography problem using multiplication of a whole number and a fraction mod 10.
Here is the equation:
7 * (4/11) mod 10 =?
I know I am supposed to convert this to an integer since the mod operator does not work with fractions, but I cannot figure this one out. Obviously,
7 * (4/11) = 28/11,
but I cannot get the mod 10 of a fraction. The instructor wants the exact answer, not a decimal. Any help would be greatly appreciated!
311
To find what number modulo n this fraction represents, you need to evaluate b−1. You can do that by using the Euclidean algorithm to solve the Bézout equation bx+ny=1. The x in this equation will give you b−1. If you know the factorization of n you can also use Euler's totient function by noting that b−1≡bφ(n)−1(modn).
Sure. In the rational numbers, 1/3 represents the solution to 3 * x = 1. For integers mod 5, we mean the same thing: 3 * x = 1 mod 5. But you can see that 3 * 2 = 1 mod 5, so 3^-1 is just 2.
Property of Exponentiation in Modular Arithmetic:a k = ( N p + b ) k = ∑ i = 0 k ( k i ) ( N p ) k − i b i . a^{k} = (Np + b)^{k} = \sum_{i = 0}^{k}\binom{k}{i}(Np)^{k-i}b^{i}. ak=(Np+b)k=i=0∑k(ik)(Np)k−ibi.
Modular arithmetic is a special type of arithmetic that involves only integers.
8 is the correct answer indeed.
7*4/11 mod 10 means we're looking at 7*4*x mod 10 where x is the modular inverse of 11 modulo 10, which means that 11*x mod 10 = 1.
This is true for x=1 (11*1 mod 10 = 1)
So 7*4*x mod 10 becomes 7*4*1 mod 10 which is 28 mod 10 = 8
133
Have a look here: "Is it possible to do modulo of a fraction" on math.stackexchange.com.
One natural way to define the modular function is
a (mod b) = a − b ⌊a / b⌋
where ⌊⋅⌋ denotes the floor function. This is the approach used in the influential book Concrete Mathematics by Graham, Knuth, Patashnik.
This will give you 1/2(mod3)=1/2.
To work through your problem, you have a = 7 * (4/11) = 28/11, and b = 10.
a / b = (28/11)/10 = 0.25454545...
⌊a/b⌋ = 0
b ⌊a/b⌋ = 0 * 0 = 0
a - b ⌊a/b⌋ = 28/11 - 0 = 28/11
This means your answer is 28/11.
Wolfram Alpha agrees with me and gives 28/11 as the exact result. Google also agrees, but gives it as a decimal, 2.54545454.....
A fraction is an exact answer and not a decimal.
39
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
