Modular Arithmetic Puns

I've been learning about modular arithmetic for years but I just can't wrap my head around it. I need a decent modular arithmetic explanation. Modular arithmetic for dummies.

https://imgpile.com/i/UyS3qN

I dont understand any of the steps at all, it would really help if I got an explanation for each step, or at least what rule they use so I can research about it more

thank you

I was reading Jacobson’s notes on Abstract Algebra, and he said something surprising about “modulo”.

Let (G, +) be a group acting on S, and let H be a subgroup of G. Let x and y be elements of S such that y = x + h for some h in H. This relation is reflexive, symmetric, and transitive. Thus, it partitions S into disjoint equivalence classes called “transitivity sets of S relative to H”. We may write x ~ y (mod H) iff y = x + h for some h in H.

For example, “1 ~ 5 mod 4”, is shorthand for “1 ~ 5 (mod [4])”. By that we mean (considering the integers under addition), “5 is a member of the transitivity set determined by the subgroup generated by 4”.

I’m really quite a layman in math, so I guess the generalization of modulo surprised me. I only saw it (notationally) in the context of modular arithmetic. But of course, with every generalization, there must be uses for modulo outside of modular arithmetic. Can you modulo Ideals in Rings? Can you modulo wackier structures? Can you modulo by the poop generated by my dog?

Hello r/learnmath. I was thinking about this proof that to see if a number is divisible by 11, the alternating sum should be so as well.

Example:

To see if the number 9845 is divisible by 11, sum them up alternating.

So, 9*(-1), + 8*1+ 4*(-1) * 5*1, and if that's divisible by 11, so should the number.

This is because:

9000+800+40+5 or 9*1000+8*100+4*10+5 in mod 11 is 9*-1+8*1+4*-1+5*1. This should equal 0 mod 11 as any number as 0 mod 11 is divisible by 11 (except 0, I guess).

I can see how it applies when thinking of it in terms of modular arithmetic, but how come it works even when the numbers are written in the original base without modular arithmetic? I hope I make sense.

I can't see how it works when you're doing it without modular arithmetic.

Also, how come 1000 mod 11 is -1? I thought it would've been 10 mod 11, as the remainder is 10 when divided by 11.

Thank you.

Hi!!! I am a first year student of Mathematics and I'm learning about basic modular arithmetic. Reading about it on Wikipedia I have found this proposition and I don't know what means (c,n)=1. Thanks in advance!!!

Proposition 5: a,b,c€Z; n€N.

ac≡bc (mod n); (c,n)=1 then a≡b (mod n)

I created this by accident when trying to make something for one of my classes. I thought it was pretty.

1000 dots spaced evenly around a circle numbered 0 through 999. The dot numbered x is connected by a segment to dot numbered kx (mod 1000). I created an animation with k ranging from 2 to 200 and this was the result.

https://i.redd.it/k9d2rags2hu71.gif

4^(2) = 4^(6) = 4^(10) = x mod a (edit)

All are equal to each other. How come?

Even if I replace it with 3 the same thing is true. This is blowing my mind but why?

Something about shifting the exponents 4 steps yields this result. Doesn't work with +3 for instance.

Examples:

3^2 mod 15 = 3^6 mod 15 = 3^10 mod 15 = 9

4^2 mod 8 = 4^6 mod 8 = 4^10 mod 8 = 0

7^2 mod 8 = 7^6 mod 8 = 7^10 mod 8 = 1

The problem is as follows: given 12 consecutive integers, in how many ways can you choose three of these integers to give a sum that is divisible by 4?

My approach was to do different cases using modular arithmetic, however, a friend showed me their solution and it seems to work. Their approach was this:

There are 220 ways of choosing 3 numbers from 12 (12C3). Since there are 4 different conferences in modulo 4, we can simply divide 220 by 4 and get 55 different ways of choosing.

Can anyone explain to me why this works? It might be something obvious but I wouldn’t have thought that we couldn’t divide by 4 if we were considering taking the sum of three integers at a time (how do we know it’s distributed evenly if we do so?)

>I was watching the hamming codes part 2 video where grant said the XOR is addition mod 2.

>So I was wondering does it exists for other gates also? If so please anyone could provide the modular arithmetic for other logic gates like AND, OR, NOT, NAND, NOR, XNOR.

>I asked this question in stack exchange but it was closed and some people said this is not a good question and was of elementary Boolean logic.

>As an electrical engineer I know how they work in digital circuits but I don't know the mathematics behind it.

My question is I have to find the remainder of 34^34 divided by 12. I then said 34^34 is equivalent to -2^34 (mod 12), and using substitution I got 4 as the remainder. Is that right?

Can anyone either help me or direct me to a resource that's going to help me understand/prove that a^m is equivalent to b^m (mod n) given that a is equivalent to b

Gallery showing the interface and some example images. Here is the GitHub project page.

I've been interested in a particular fractal-generation method for a while and just finished my master's thesis on the subject. I decided to make and share an interactive version of the picture-making program I used so I can spread my fascination. In short, these are all variations on how color-coding the odd and even entries of Pascal's triangle generates the Sierpinski triangle fractal. I have a bit more explanation on the GitHub page.

This was my first time programming a GUI and I'm completely self-taught when it comes to programming, so I welcome advice and feedback.

Hi Guys, as the title says, I need someone to double check this proof, Im far from an expert on induction and probably haven't set it out in the neatest way so id appreciate any feedback.

Thanks in advance!

https://preview.redd.it/h2zdpt3r6fc71.png?width=508&format=png&auto=webp&s=e1fc87d069df8d2bfaf7dd3bc1f26423bb2b15cd

What's the best way to make a python script to brute force little modular arithmetic numbers and where can i find examples?

Here's what i mean:

>37 ** x = 18 % 41

Brute force 41 to find x.... Or some modifications to cut the time instead . I couldn't specifically find one in the vast web specifically for modular arithmetic. Your thoughts on this would be appreciated.

N.B : Posted a question about this but it didn't get answers. So please do consider this as a repost.

Edit : Changed 37**x = 28 % 41 to 37**x = 18 % 41

Imgur: The magic of the Internet

I don't quite understand how we go from 81 to 7 to 7 x 49

UPDATE: Versus AI mode added.

Free, web-based, mobile friendly-ish. The gameplay revolves around knowing modular multiplication.

If you're a starter number theorist - might be a good way to practice it.

If you know it perfectly (specifically modulo primes 5-31) - there are still ways to outplay or to be outplayed by your opponent.

https://nikita-dezhic.itch.io/cards-mod-prime

https://preview.redd.it/lnew3rni8xg71.png?width=1440&format=png&auto=webp&s=7c8742d7344ff5dc8c6a28f9960735817f5698de

For example, how would you solve 44^-1(mod667)? After calculating phi(667), you end up with 44^615(mod667), which would take ridiculously long to calculate without a calculator. And even then, most calculators cannot even go that high.

Hi - This is my first blog post - Why Polynomial Modular Arithmetic in Finite Fields?

This is my first attempt at writing about something in Crytography.

I am pretty new to Abstract Algebra & Elementary Number Theory & when I was trying to learn by reading some books in the last few months, this was one question I couldn't find answered formally in any book - The Math books talk about Finite Fields but don't link it to why it's used in Cryptography. The Cryptography books also don't talk much about it.

Since I am pretty new to Abstract Algebra, I am pretty sure there are lot of mistakes in the post - so please feel free to point it out - that's the main reason I am posting it here.

Hello! I'm a relatively new coder. I'm in a number theory class and wanted to use an algorithm to help solve some linear congruences.

I tried searching for functions in Julia but the only thing I found was a modular arithmetic package with the Chinese Remainder Theorem. I'm not looking to solve a whole system, just one congruence of the form ax = 1 mod n where a is known.

Is there function for this already? It should be easy to write (just have to write the Euclidean algorithm and the back-substitution), but I wanted to check before I tried. Thanks!

I want to implement modular arithmetic of cryptographically large numbers. What this precisely means is slightly up for debate (I am not particularly interested in RSA, so do not exactly need ~4k bit arithmetic), but the main idea is that I cannot simply fit everything into primitive types.

The base of most big-int algorithms is a representing a number (say a u320) as something like a [u32; 10] or [u64; 5], where each individual u32 or u64 is a "digit" (known as a limb) of the base-W expansion of the number, where W is some specific u32 or u64 value (typically something like 2^31 or 2^63). As I want to implement a general library, we may as well define something like a:

struct BigInt<const N : usize>([u32;N]);

as our basic type.

Now, for modular arithmetic, it would be fairly bad if you did something like add together two numbers that are residues mod different numbers (it is just mathematically not well defined). This is to say that (x % N) + (y % M) should be a type error, and fail to compile. For small moduli (say anything that one can fit into a u128) one can enforce this with min-const-generics, but for larger moduli than that I'm having issues thinking of the right thing to do.

It would be ideal if one could write:

struct Modular<const N: usize, const MODULUS : BigInt<N>>(BigInt<N>);

but this does not work due to error E0770. This post is essentially asking for advice about what to do to work around this error.

My main ideas so far are one of the two:

1. Restrict to moduli of a special form (2^EXP +/- OFFSET), which one can encode into the type system using:

struct Modular<const N: usize, const EXP: u16, const OFFSET: isize>(BigInt<N>);

This is mostly fine for my purposes (as I am not interested in RSA in particular), but having to write that type signature on each impl block kind of sucks, and while this kind of optimization is probably good to support eventually having something that "just works" for any choice of parameters is probably a good first goal.

2. Stick the moduli into Modular itself, and do run-time checks. The idea of ensuring correctness at run-time kind of sucks, but one could always stick checking the equality of the moduli of operands within a debug_assert!() or something to minimize the runtime cost (you could even do things like compare if the references are literally the same pointer t

Hey all.

I'm gearing up to take this test soon. I have seen very mixed responses about this OA. Some individuals think this OA was very similar to the PA, some think it was in a whole different league. That being said, typically on math/cs related OA's I have found there is 2-3 big concepts to grasp that if known well can usually yield a passing score.

SO, out of your C960 OA, which concepts yielded the most questions? Algorithm solving, RCA, Modular Arithmetic, Bayes? Or was a it a perfect mix of all? You tell me! Thanks all! All last minute tips are welcome.

This is a link to my blogpost - https://risencrypto.github.io/FiniteFields/

> Polynomial Modular Arithmetic done in Finite Fields is used in a lot of places in Cryptography - for e.g. in AES/Rijndael, GHASH, POLYVAL etc. What is the reason for this?

I am pretty new to Abstract Algebra & Elementary Number Theory. When I was trying to learn by reading some books in the last few months, this was one question I couldn't find answered formally in any book. My blog post answers the question.

What's the best way to make a python script to brute force little modular arithmetic numbers and where can i find examples?

Edit: Here's what i mean;

>37 ** x = 28 % 41

Brute force 41 to find x.... Or some modifications instead. Your opinions are essential.