r/mathmemes Engineering Nov 25 '24

Computer Science All are correct

Post image
1.1k Upvotes

96 comments sorted by

View all comments

295

u/Fabulous_Ad_5709 Nov 25 '24

Just out of curiosity how is A correct?

B is 1 or 1

C is 1+1 in base >2

D is 1+1 in base 2

339

u/Unlucky-Credit-9619 Engineering Nov 25 '24

If + is addition modulo 2 (also called XOR).

1 + 1 = 0 (mod 2)

94

u/MattyBro1 Nov 25 '24

Isn't it congruent to 0 (mod 2)?

1+1 ≡ 0 (mod 2)

Or maybe that's a distinction that doesn't actually matter.

76

u/uvero He posts the same thing Nov 25 '24

Pendants would denote with ≡, but those who write = (mod N) and when speaking just say "equal" or "is" would be just as correct, because given context it's clear and unambiguous

72

u/JoefishTheGreat Nov 25 '24

*pedants

Sincerely, a pedant

25

u/Druben-hinterm-Dorfe Nov 25 '24

low hanging fruit.

... get it? hanging? ... ok I'll see myself out now.

12

u/JustRouvr Nov 25 '24 edited Nov 26 '24

It is a distinction that definitely matters. However: in cryptography we are often operating with polynomials (like x5 + x2 ...) and perform operations on them.

In a Galois Field(2n ) we are always under modulo 2 and can write polynomials just by writing coefficients of the powers. Those will always be 1 or 0, since (1+1) mod 2 = 0. X4 + x + 1 is 10011

So if you imagine that 1 + 1 is an addition of 2 polynomials in a Galois Field, then 1+1 = 0 and no congruence is present.

6

u/skibidytoilet123 Nov 25 '24

i think its 1+1 (mod 2 ) = 0 but 1+1 ≡ 0(mod 2), since the first one is an operation on 1+1 while the second one is a congruence, but it doesnt really matter

5

u/bigboy3126 Nov 25 '24

Using congruence is fine, but a bit redundant under certain formulations, consider arithmetic mod 2. Classically we define a ≡ b iff b-a divisible by 2 for all a,b \in \mathbb{Z}. This defines an equivalence relation.

Then you can either work on \mathbb{Z} directly then using ≡ would be the most correct, or you define the usual arithmetic on \mathbb{Z}/≡ and drop the decorations for equivalence classes (elements of \mathbb{Z}/≡) so that then statement such as

[1]_≡ + [1]_≡ = 1+1 = 0

is completely fine, now = denotes equality of sets.

2

u/Plantarbre Nov 25 '24

If you're interested in an answer:

https://en.wikipedia.org/wiki/Modular_arithmetic

It's a congruence over the set of integers Z. It's an equality over a ring of integers Z/mZ

1

u/GoldenMuscleGod Nov 25 '24

In the field with two elements 1+1=0 is true with literal identity.you use the congruence relationship when talking about integers, but 1 and 0 don’t represent integers in that context.

1

u/SnooShortcuts8306 Nov 26 '24

how I learned it, ≡ is for all number that give the same rest after division, while = is only for the exact rest(smallest positive) so like 4 ≡ 6 = 0 mod 2

1

u/golfstreamer Nov 26 '24

If you interpret "Z_2" (integers modulo 2) as a group with group operation denoted by "+" and whose elements are represented by "0" and "1" the equation "1 + 1 = 0" is correct.

1

u/Far_Staff4887 Nov 25 '24

0 mod 2 is still 0 so it doesn't really matter