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
6
votes
5 answers

Solving simultaneous congruences

Trying to figure out how to solve linear congruence by following through the sample solution to the following problem: $x \equiv 3$ (mod $7$) $x \equiv 2$ (mod $5$) $x \equiv 1$ (mod $3$) Let: $n_1$ = 7 $n_2 = 5$ $n_3 = 3$ $N = n_1 \cdot n_2…
Arvin
  • 1,733
6
votes
2 answers

Prove $(a + b) \bmod n = (a \bmod n + b \bmod n) \bmod n$

I find I am in trouble to prove: $$(a + b) \bmod n = (a \bmod n + b \bmod n) \bmod n ?$$ Can anyone help?
Wei Zhong
  • 457
6
votes
2 answers

Tribonacci sequence modulo X

The Tribonacci sequence satisfies $$T(n) = T(n-1) + T(n-2) + T(n-3)$$ with $T(0)=0$, $T(1)=1$, $T(2)=1$. I need to calculate $T(y) \mod 10000$ for $y > 2^{40}$. How can I make this faster? I know that this is periodic in…
florian
  • 63
6
votes
2 answers

Efficient way to find $a$ in $c = 6a\mod n$

Given $c$ and $n$ in $c = 6a\mod n$, how can I find the lowest positive integer value for $a$? I could find it iteratively by rewriting as $\displaystyle a = \frac{c + xn}{6}$ and increasing $x$ until $a$ is an integer, but I would prefer a more…
jnm2
  • 3,170
6
votes
2 answers

Prove that $n|2^{(n-1)!}-1$ for any $n = 2k + 1$ given $k$ is a natural number

What i have done so for: $2^{(n-1)!} \equiv 1 (mod\hspace 1 mmn)$ Thought about wilson`s theorem but $n$ is not a prime. Tried to break the factorial and reduce the congruence to $2^{(n-2)!}$ but not sure this is the right way to do. Any advice…
Mabadai
  • 369
6
votes
2 answers

Solving equations involving modulo operator

In computer programming languages we have an operator called % which expresses the remainder between two numbers. For example $123\%100 = 23$. I have an equation evolving this operator, namely, $$\frac{5}{3}(N\%36) - \frac{2}{3}(N\%6) + 2(N\%25)…
Mark
  • 5,696
6
votes
1 answer

$N$'s base-5 and base-6 representations, treated as base-10, yield sum $S$. For which $N$ are $S$'s rightmost two digits the same as $2N$'s?

Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-10 integers, he adds them to obtain an…
Max0815
  • 3,505
6
votes
9 answers

Why does a number like $2^n\bmod 7$ have a repeating pattern?

I am struggling with the formal understanding of why a number like $2^n\bmod7$ have a repeating pattern? $1, 2, 4, 1, 2 ,4\ldots$ The repeating pattern show up in many places of modular arithmetic, what is the primary reason for this? Thank you
6
votes
1 answer

Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$?

Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$ ? I know polynomials do; are there others?
aaa
  • 586
6
votes
1 answer

Tell whether $(1234657)! +1 \equiv_{11111} (7654321)! -1$ is true or false

I have to tell if the following is true or false: $$(1234657)! +1 \equiv_{11111} (7654321)! -1$$ so by definition we can rewrite the previous equivalence as: $(1 \cdot 2 \cdot \ldots \cdot 11110 \cdot 11112 \cdot \ldots \cdot 1234567) \cdot 11111 +1…
haunted85
  • 1,418
6
votes
4 answers

Modulus of negative numbers

I had a doubt regarding the ‘mod’ operator So far I thought that modulus referred to the remainder, for example $8 \mod 6 = 2$ The same way, $6 \mod 8 = 6$, since $8\cdot 0=0$ and $6$ remains. When I perform an operation such as 1) $-8 \mod 6 =…
6
votes
3 answers

How can I prove that an order ("$<$" say) on $\mathbb Z_n$ cannot be defined?

I'm trying to show why it isn't possible to define an order of magnitude on $\mathbb Z_n$ (modular arithmetic) that satisfies the ordering properties of $\mathbb Z$. By letting addition to be $\oplus$ and multiplication $\otimes$, I know the…
leqs
  • 117
6
votes
3 answers

$2^{1008} \mod 2017$

Find $2^{1008} \mod 2017$ From Fermat's we can find that $2^{2016} \equiv 1 \mod 2017$. But now we cant say that $2^{1008} \equiv 1 \mod 2017$. It can be $-1$ too. But how to prove that it is equal to $1$?
6
votes
3 answers

Where is the mathematical logic with this exponent behaviour?

I'm learning how the diffie-hellman key exchange algorithm, works and I came to a mathematical conflict which I can't understand its logic . This is the story: ( yuu can bypass this , it's just a brief) Alice and Bob wants to generate the same…
6
votes
1 answer

Why can we exchange numbers when working with modulo expressions?

Please excuse me if the answer is obvious because I'm a beginner. Why can we exchange numbers when working with modulo expressions? For example: $$4^2 \equiv (-1)^2 \pmod{5}$$ You may say the replacement between $4$ and $-1$ is justified…