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
1 answer

Calculate $2^{1401} \pmod{2803}$

Without using the fact that 2803 is prime, Calculate $2^{1401} \pmod{2803}$ Usually I would do something like: $1401 = 3\times467$ $\equiv(2^{467})^3 \pmod{2803}$ And try to simplify it down and use the mod to get it down to something I can punch…
Arvin
  • 1,733
1
vote
2 answers

How do I prove this division formula (decimal modular arithmetic)?

I was doing some poking around by extending a math problem I got for homework. I found that if you have any number of only digits of 3, q = 33...3, the smallest number of all 1s, p = 11...1 such that p = 0*mod(q) has to be the number p = 11...1 with…
1
vote
3 answers

Simplifying $(p-1)! + (p-2)! + (p-3)! + (p-4)! + (p-5)! \bmod p$

Trying to get the modulus of the five numbers immediately before a prime, added together in there factorial form; I'll call this operation $S(p)$. For example, $$S(p) = ((p-1)! + (p-2)! + (p-3)! + (p-4)! + (p-5)!) \bmod p$$ $$S(5) = (4!+3!+2!+1!+0!)…
Dan
  • 11
1
vote
3 answers

modular arithmetics - remainder

I need to find the remainder of ${1011}^{10}+{10}^{11}$ when divided by $101$. According to this website it is 55 but I fail to see how. For 1011, we can write it as $1$ because $1011=10*101+1$ so ${1011}^{10}$ is $1$. For ${10}^{11}$, I wrote the…
Lumon
  • 85
1
vote
2 answers

Modulo of negative numbers with squares

I'm trying to find $10^{11} \mod 101$. Here's what I did: $\pmod{101}$ However, the calculator shows that $10^{11}\equiv91\pmod{101}$ Where did I go wrong?
blz
  • 615
1
vote
1 answer

Equation $a+k \pmod{b+k} = 0$ and the smallest $k$

We let's equation: $a+k \pmod{b+k} = 0$ For example: $a = 153$; $b = 52$; We are looking for the smallest $k$ giving solution $153+k \pmod {52+k} = 0$ The correct result is $k=49$ becouse: $153+49 \pmod {52+49} = 202 \pmod {101} = 0$ What is the…
Aurelio
  • 479
1
vote
2 answers

Modular arithmetic three variables

Show that if the integers $x, y,$ and $z$ satisfy $x^3 + 3y^3 = 9z^3$ then $x = y = z = 0.$ How should I interpret this question and how to proceed? I am thinking about the Euclidean algorithm but it becomes confusing when $x,y,z$ comes like…
1
vote
2 answers

FInd the missing digit in $2^{29}$ given all nine digits differ

The number $2^{29}$ has (in base $10$) $9$ digits, all different. Which digit is missing? I think about using fermats theorem dosen't know how to begin
1
vote
4 answers

How to simplify $\frac{n^n - 1}{n - 1} \mod (n + 1)$?

My question is how to simplify the following: $$\frac{n^n - 1}{n - 1} \mod (n + 1)$$ I've tried a bunch of tricks (splitting into even and odd $n$ and using a difference of squares) but I can't seem to find anything that gives a clean answer. Is…
Cisplatin
  • 4,675
  • 7
  • 33
  • 58
1
vote
3 answers

Remainder in this case using modular arithmetic

How do you find the remainder when $870^{479}$ is divided by 65? My approach: $870\equiv 25\pmod {65}$ =>$174^{479}\equiv 5^{479}\pmod {13}$ =>$174^{479}\equiv 25^{234.5}\pmod {13}$ I am stuck here. Please help.
MrAP
  • 3,003
1
vote
1 answer

How can I calculate the $n$-th root of a number modulo $m$?

I have to calculate the $n$-th root of a number $x$ modulo $m$: $$\sqrt[n]{x} = a\quad \mod(m),$$ where $x$, $n$ as well as $m$ are known. The only unknown number is $a$. It would already help me a lot, if I could convert it to a type of problem…
xxsl
  • 99
1
vote
1 answer

Can modular algebra be conducted exactly as algebra typically is?

An example for those that might not understand my question: $[4][x]+[8]=[1]$ in $\mathbb{Z}_9$ My initial reaction is to make this: $[4][x]=[-7]$ $[x]=[-7]/[4]$ Then I would determine what $[-7]$ and $[-4]$ is in $\mathbb{Z}_9$ and divide those…
P_Drach
  • 19
1
vote
2 answers

Solving Linear Congruence

Ok, I found a lot of questions asking about solving $a = b \pmod c$ where you could divide $a$ and $b$ by some $x$ where gcd$(x, c) = 1$. How do you solve when this is not the case? Suppose I have $10 x \equiv 5 \pmod{15}$. How do I solve this? How…
1
vote
6 answers

How is $3\equiv 3\bmod{5}$

Just tried googling but couldn't find any example, but how $3\equiv 3\bmod{5}$ Googled it
tereško
  • 157
1
vote
1 answer

Is this rewrite correct?

If x mod 9 = 1, can I rewrite the equation as x = 1 mod 9. If not, what is the correct way? I know this sounds silly. But please help me.