Questions tagged [modular-arithmetic]

Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $a-b$.

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $a-b$. In modular arithmetic, one can add, subtract, multiply, and exponentiate but not divide in general. The Euclidean Algorithm, the Chinese Remainder Theorem, and Fermat's Little Theorem are important throughout mathematics. Modular exponentiation plays an important role in cryptography nowadays.

11320 questions
2
votes
1 answer

a mod -b (Maple disagrees with Wolfram)

According to my professor (and maple) a mod -b such as 1000%(-9) Is an invalid question that cannot be answered, since c>0, he claimed also that Maple will respond with "Error, invalid mod". However, Wolfram Alpha will respond with -8, a negative…
Manumit
  • 203
2
votes
2 answers

Using modular arithmetic, how can one quickly find the natural number n for which $n^5 = 27^5 + 84^5 + 110^5 + 133^5$?

Using modular arithmetic, how can one quickly find the natural number n for which $n^5 = 27^5 + 84^5 + 110^5 + 133^5$? I tried factoring individual components out, but it seemed really tedious.
David Faux
  • 3,425
2
votes
1 answer

Unfamiliar Property of Modular Arithmetic

I saw this property listed in Princeton Review's Math GRE book: "For any positive integer $c$, the statement $a\equiv b\mod n$ is equivalent to the congruences $a\equiv b,b+n,b+2n,\ldots,b+(c-1)n\mod cn$." Now, my problem is that I have no idea what…
428
  • 565
2
votes
0 answers

Generalized modulo arithmetic

This question (and especially this answer and the comments on it) actually made me think about a sort of generalized modulo arithmetic that would deal with all modulos at once and would basically make all the notations equally valid. Here's the…
celtschk
  • 43,384
2
votes
4 answers

Modular maths: How do I find the remainder?

How do I find the remainder of $5^{22} \pmod{25}$? And also how do I find the remainder of $3^{16} + 7 \pmod{5}$?
User95
  • 121
2
votes
1 answer

Modulo of squared number

I have tested a lot of combinations with integer numbers and it seems like we can say that $y^2 \bmod n$ equals $((y \bmod n)^2) \bmod n$. I can't find any resource that acknowledges this. Is my statement correct? If no, what are the corner cases,…
Housy
  • 123
2
votes
2 answers

Eggs in a Basket (Remainders)

I'm working on a problem: A woman has a basket of eggs and she drops them all. All she knows is that when she puts them in groups of 2, 3, 4, 5, and 6, there is one left over. When she puts them into groups of 7, there are none left over. What is…
2
votes
2 answers

Do inequations exist with congruences?

Gauss introduced the $\equiv$ symbol because congruences modulo $n$ were very similar to equality. But, by curiosity I would like to know if it was possible to write inequations such as: $$3x + 2y \leq 5 [7]$$.
lopata
  • 319
2
votes
4 answers

Find the identity under a given binary operation

I have two problems quite similar. The first: In $\mathbb{Z}_8$ find the identity of the following commutative operation: $$\overline{a}\cdot\overline{c}=\overline{a}+\overline{c}+2\overline{a}\overline{c}$$ I…
BAD_SEED
  • 463
2
votes
2 answers

Can $ 2^{3^{4^{.^{.^{.^{n-1}}}}}}\equiv 1 \bmod {n} $ for some $n>7$.

Prove or disprove that there isn't any positive integer $n>7$ such that the linear congruence below is true. $ 2^{3^{4^{.^{.^{.^{n-1}}}}}}\equiv 1 \bmod {n} $
GohP.iHan
  • 1,376
2
votes
3 answers

A bunch of questions on $\mathbb{Z}_n$

I'm studying the remainder class $\mathbb{Z}_n$, I've grabbed something, but something else is unfocused. Let $$20x \equiv 4\pmod{34}$$ then GCD(20,34)=2 so I rewrite as: $$10x \equiv 2\pmod{17}$$ and successively: $$10x \equiv 1\pmod{17}$$ Now I…
BAD_SEED
  • 463
2
votes
1 answer

Computing $\frac{n^2(n + 1)}2 \bmod m$

How to calculate $$\frac{n^2(n + 1)}2 \bmod m$$ where $1 \leq n \leq 10^{16}$ and $1 \leq m \leq 10^7$? Here $m$ and $n$ are integers. What I have done: if n is even: $$\frac{n^2(n + 1)}2 \bmod m = {(\frac{n}{2} \bmod m)(n\bmod m)((n + 1) \bmod m)} …
Sud
  • 21
2
votes
4 answers

$(a+b)^p \equiv a^p + b^p (\mod p)$. Proof.

Let $p$ be prime, $a,b \in \mathbb{Z}$. Prove that: $$(a+b)^p \equiv a^p + b^p\pmod p$$ How to deal with it.
user180834
  • 1,453
2
votes
1 answer

Modular Arithmetic, Pythagorean triples

I'm not sure if this question should be under Modular Arithmetic, but that's where it was in my book. Show that, if $x$, $y$, and $z$ and integers such that $x^2 + y^2 = z^2$, then at least one of $\{x, y, z\}$ is divisible by $2$, at least one of…
2
votes
1 answer

Modular expression and my trying.

Is it a true:? $$\begin{cases} 2x \equiv 2 \mod 5 \\ 3x \equiv 2 \mod 4 \\5x \equiv 2 \mod 6\end{cases}$$ $$2x \equiv 2 \mod 5 \iff x \equiv 1 \mod 5 $$ $$3x \equiv 2 \mod 4 \iff 6x \equiv 4 \mod 4 \iff 3x \equiv 2 \mod 2 \iff x\equiv 0 \mod 2 …
user180834
  • 1,453