Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

## Hot answers tagged modular-arithmetic

5

Consider the first few powers of 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024… Now take all of those mod 10: 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4… Try to solve it yourself, from this, before continuing to read. There's a theorem that says, if $x \times y \cong z \mod m$, then $x' \times y \cong z \mod m$, for any $x' \cong x \mod m$. This means that, ...

4

Write down the first 10 or so powers modulo 10. Do you see a pattern?

4

Remainder modulo 10 instead of last digit What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10. For simplicity, we will compute the value of polynomial modulo 10. We will just say "the remainder of some number" to mean the least positive remainder of that number divided by 10. (The idea and ...

3

The low bits of a linear congruential generator are notoriously weak. Try to use only the higher order bits. Normally this is done by bit operations, but you can discard the bottom $b$ bits by dividing by $2^b$ and rounding down.

3

$$2^N \bmod 10 = 2^{(N-1) \bmod 4 + 1} \bmod 10$$ (try to prove it)

2

What's exactly "trial and error method" applied in this situation? $\newcommand{\mymod}{\operatorname{modulo}}$As I understand, "trial and error method" here means checking all cases from a few simple natural or known perspectives until we have found a satisfactory solution or proof. It is useful and efficient in this situation because the number of cases $\... 2 One algorithm to compute inverses in a finite field is to raise to a large power. In particular,$x^{-1} = x^{p-2}$if you are working in$\mathbb{F}_p$(by Fermat's little theorem). You can use standard algorithms for fast modular exponentiation to compute this with about$2 \lg p$multiplications, or fewer (depending on the specific value of$p$and the ... 2 The standard algorithm for inverting an element is using the extended Euclidean algorithm. You can read all about this connection on Wikipedia. 2 My knowledge in Latin and etymology is very limited, but, 'modulus' is a Latin word, and the form 'modulus' is singular, nominative. 'moduli' is its plural form, again in the nominative case. Finally, 'modulo' is its ablative case. I believe that 'a is congruent to b modulo m' literally means something like 'a is congruent to b in the modulus m'. English ... 2 It's even a bit simpler, namely both: a <u b == (a ^ m) <s (b ^ m), and, a <s b == (a ^ m) <u (b ^ m) Where m is the mask with the sign bit set. I don't have a formal proof for that, but the image below shows what is happening. The top row shows the "unsigned order" of the number line, chopped in half, with the first part having a 0 in the top ... 2 You might be confusing the ring and the multiplicative group of invertible elements mod p. The first one is isomorphic to the integers from 0 to p-1, 0 being the additive neutral element, and 1 being the multiplicative neutral element. If p is prime, the intervible elements are the integers from 1 to p-1, and they form a multiplicative group. By the way, ... 1 They aren't treated any different. The elements in the mod ring of any integer x include all numbers in the range [0,x-1]. However, different programming languages treat negative numbers in different ways. (-5) MOD 3 = 1 in Python. whereas, (-5) MOD 3 = -2 in C. This problem can be solved by simply adding the value to the negative result. In this case ... 1 We have$z^\lambda$has the form of $$f(z)u(z) + p^ev(z) + 1$$ where$p^{e+1}\mid f(z)u(z),f(z)\mid p^ev(z)$and$v(z)\not\equiv 0\pmod p\ $(*) You misunderstood the definition of$a(z)\equiv b(z)\pmod {f(z)\text { and }m}$. If$z^\lambda \equiv 1 \pmod{ f(z)\text{ and }p^{e}}$, then $$z^\lambda=1 + f(z)u(z) + p^ev(z)$$ for some$u(z), v(z)$. There ... 1 Since$10$is relatively prime to$M$, it has an inverse modulo$M$, which can be found efficiently using the extended GCD algorithm. So you can simply calculate$X = -10^{-L}D$(all computations modulo$M\$).

Only top voted, non community-wiki answers of a minimum length are eligible