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
1
vote
3 answers

Elementary question on modular arithmetic

I know, this is very simple and dumb question, i just cannot come to understand, the problem is: Why and how happens this in mathematics? $$-5\equiv 3\pmod 4$$ I know how to get this for positive numbers, but how does it work for negative ones. I…
doniyor
  • 3,700
1
vote
3 answers

Number reduction before mod

$$15\cdot25 \pmod {11}\equiv 4\cdot3 \pmod {11}$$ How does it work? Full example $$3^{(11-1)} \pmod{11} = 3\cdot27\cdot27\cdot27 \pmod{11}= 3\cdot5\cdot5\cdot5 \pmod{11} = 15\cdot25 \pmod{11}= 4\cdot3 \pmod{11} =1 \pmod{11}$$
Kopkan
  • 113
1
vote
4 answers

What is the reason behind using MOD equivalence notation?

If the notation $$a \equiv b \pmod{n}$$ means (a%n) = b, then why don't we just use $(a\%b) = b$ as the notation instead of using $a \equiv b \pmod{n}$ ?
1
vote
1 answer

solving a problem on dividing items into piles

there have been many complex modular arithmetic problems, like this one from a book i read, called 1001 mathematics(great book on math, i must say): A girl has a certain number of pennies. When they are divided in 5's, 3 are left over. when they…
1
vote
1 answer

Solve for x in $a = x^b$ (mod n)

I would like to solve for $x$ in $a = x^b\ (mod\ n)$ given $a$, $b$, $n$. How might I go about doing this?
1
vote
2 answers

All 3 digit numbers are written into one long number $N=100101102...999$. Find $N \pmod {210}$.

I have no idea how to solve this, but I feel that $210=2\times3\times5\times7$ has something to do with the problem.
Gerard L.
  • 2,536
1
vote
1 answer

Converting Decimal number to 10's complement

Is there any other way to convert a decimal number to 10's complement without substraction? Not this method: Converting 052784: 100000-052784 = 947216
Tugkan
  • 35
  • 1
  • 4
1
vote
1 answer

Assume $d\mid n$. Show $g\colon (\mathbb Z/n\mathbb Z)^*\to(\mathbb Z/d\mathbb Z)^*$ given by $g(a\mod n)= a\mod d$ is surjective.

Let $d,n\in\mathbb Z_{>0}$ with $d\mid n$. Show $g\colon (\mathbb Z/n\mathbb Z)^*\to(\mathbb Z/d\mathbb Z)^*$ given by $g(a\mod n)= a\mod d$ is surjective. In a previous exercise, I’ve shown the following: Let $d,n\in\mathbb Z_{>0}$ with $d\mid…
Sha Vuklia
  • 3,960
  • 4
  • 19
  • 37
1
vote
3 answers

Evaluate congruences with non-prime divisor with Fermat's Little Theorem

I can evaluate $ 17^{2012}\bmod13$ with Fermat's little theorem because $13$ is a prime number. (Fermat's Little theorem says $a^{p-1}\bmod p\equiv1$.) But what if when I need to evaluate for example $12^{1729}\bmod 36$? in this case, $36$ is not a…
xiamx
  • 449
1
vote
3 answers

How can I solve for mod to get a value?

I want to solve the following part involving mod: 1 = -5(19) (mod 96) Apparently, this mod in brackets (mod 96) here is different from the mod that I know e.g. its not the remainder value that you get by dividing. What of kind of mod is it and how…
1
vote
2 answers

Prove $\left[x \operatorname{mod} 2^w+ x \operatorname{div} 2^w\right] \operatorname{mod} (2^w -1) = x \operatorname{mod}(2^w -1)$

Been trying to prove different versions of something similar for so long now. Any help would be appreciated! EDIT: x and w are integers. $\left[x \operatorname{mod} 2^w+ x \operatorname{div} 2^w\right] \operatorname{mod} (2^w -1) = x…
1
vote
2 answers

Finding the remainder to an awful division

If $x=(11+11) \times (12+12) \times (13+13) \times\cdots \times (18+18) \times (19+19)$, what will be the remainder if $x$ is divided by $100$? I tried simplifying the expression like…
1
vote
4 answers

Modular arithmetic problem: $7^x \equiv 1 \pmod{26}$

I have the following maths question, which I would like to solve in preparation for an exam: "Find the smallest positive integer $x$ such that $7^x \equiv 1 \pmod{26}$. Calculate $7^{100} \bmod{26}$ (give your answer as a positive integer less than…
1
vote
1 answer

If $m = s + t$ then $m \pmod k \equiv (s \pmod k + t \pmod k) \pmod k$

If $m = s + t$ then $m \pmod k \equiv (s \pmod k + t \pmod k) \pmod k$ Can someone provide a proof of the above statement. I can understand it for the case of $s \equiv 0 \pmod k$ or $t \equiv 0 \pmod k$, or when both are zero, but not when neither…
1
vote
1 answer

Proof help needed about Congruences

Could you please help me to prove the following questions: Q1) Consider $ax ≡ c \pmod m$ (call it **), if $\gcd(a,m)=1$ then ** has a unique solution modulo $m$ i.e. i) ** has a solution $x_0$ ii) Any solution $x$ of ** satisfies $x ≡ x_0 \pmod…
Xentius
  • 1,151