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
0
votes
3 answers

Prove if p is a prime number that does not divide a, then $a^{p^2}$ congruent to $a^p\mod p^2$

I tried to do proof by contradiction, so I started to do use real arbitrary numbers. I decided I use p for prime still, but a being a multiple of p and by doing this, the statement is still true. I tried it with p=3, a =6 or p=2 and a =6. Anyways…
0
votes
0 answers

For all $[a]$,$[b]\in{\mathbb{Z}m}$, if $[a][b]=[0]$, then $[a]=[0]$ or $[b]=[0]$. Prove that if $S$ is true, then $m$ is prime.

Let $m\in{\mathbb{N}}$ such that $m>1$. Consider the implication $S$: For all $[a]$,$[b]\in{\mathbb{Z}m}$, if $[a][b]=[0]$, then $[a]=[0]$ or $[b]=[0]$. Prove that if $S$ is true, then $m$ is prime. How should I go about solving this implication?…
Sania
  • 103
0
votes
1 answer

Modular arithmetic: Solving equation modulo prime number

I have an equation $$x \cdot a \equiv b\pmod m$$ where $a$ and $b$ are known and $m$ is a prime number. I want to solve for $x$. If $b=1$ then $x=a^{m-2}$ but I need to solve it for any value of $b$. I found this answer which seems to work but is…
0
votes
0 answers

Simple modular arithmetic expression proof

I'm trying to prove that if $N_1\mod(a) = n_1$ and $N_2\mod(a) = n_2$ then $(N_1+N_2)\mod(a) = (n_1+n_2)\mod(a)$ By our assumption $N_1 = am_1 + n_1$ and $N_2 = am_2 + n_2$ So $N_1+N_2 = a(m_1+m_2) + n_1 + n_2$ So $(N_1+N_2)\mod(a) = (a(m_1+m_2) +…
EBL
  • 11
0
votes
3 answers

What are the last two digits of $3^{100}11^{50}+7^{518}$?

What are the last two digits of $3^{100}11^{50}+7^{518}$? I know that to find the last two digits implies that you are essentially finding the remainder when divided by $100$. Can I simplify $3^{100}$ to $3$ mod $1$ by dividing both the exponent…
macy
  • 81
  • 6
0
votes
3 answers

solving modulo equation where the mod is also a variable?

Is there a possible way to solve an equation like this? it has only 1 variable, but it is in both sides. Constraint: n must be an integer 20-3n = 0 mod (10n+7) one solution would be n=1, Can there be multiple solutions other than that?
Omar
  • 141
0
votes
1 answer

What is the remainder when $5 000 000^{500 000 000 000}$ is divided by the prime number $10^{6}+3$?

What is the remainder when $5,000, 000^{500 ,000 ,000 ,000}$ is divided by the prime number $10^{6}+3$? I tried to use Fermat's Little Theorem but the exponent is still pretty high.
suklay
  • 671
  • 4
  • 8
0
votes
2 answers

Modular arithmetic proposition

I am trying to solve this Modular arithmetic problem but I have no idea how to verify if the proposition holds or not. $\forall a,b \in \mathbb{Z}: (a \equiv b \pmod{5} \Rightarrow 2a \equiv 2b \pmod{5} )$
0
votes
1 answer

Way to speed up this modulo operation?

I need to do this for a programming contest, but I thought it would be a better fit here. I need to perform the following computation multiple times: $$ x = ((x \cdot a) + b) \% M $$ Basically I need to do: for(int i=0;i
0
votes
4 answers

Determine if there is a solution to the congruence $x^6+5x^2 \equiv 2\mod 7$

I've checked if $x = 1, 2, \ldots, 6$ and they are not congruent to $2 \mod 7$ so, $x$ would have to be a fraction if anything. How would I be able to show it?
Kayy Wang
  • 87
  • 5
0
votes
3 answers

Find the multiplicative inverse of $(5^{14})$, mod $17$. Give your answer as a number in the set {$0, 1, 2,...,16$}. Do not use a calculator.

Essentially $x$ = $1/(5^{14})$ mod 17. I've only used smaller numbers to find the inverse; now I'm getting confused on what to do with a larger number.
Kayy Wang
  • 87
  • 5
0
votes
7 answers

show that the remainder of $\frac{2^{100}}{23}$ is $2$

As stated in the title, I'm supposed to show that $$2^{100}\equiv 2 \pmod {23}$$ I can't really wrap my head around this. At first I thought the book said that $a \equiv a^x$ no matter the exponent, but this doesn't seem to hold true since $2^1,…
Magnus
  • 703
0
votes
3 answers

Inheritance of $+$ and $\cdot$ from $\mathbb{Z}$ in $\mathbb{Z}/m\mathbb{Z}$

It's rather intuitive that $[x]_m \oplus [y]_m = [x+y]_m $ and $[x]_m \otimes [y]_m = [x \cdot y]_m $. I was wondering if someone could give me a formal explanation of why $\oplus$ and $\otimes$ 'inherit' the properties of $+$ and $\cdot$. In other…
MyWorld
  • 2,398
0
votes
1 answer

Modular Exponentiation with unknown base

Consider $x^a\equiv1 \pmod n$. Is there a general way to solve for $x$, given $a$ and $n$? Would knowing the factorization of $n$ make it easier?
0
votes
0 answers

How to find modulo of negative floating point number?

I'm studying Hill Cipher and I tried to calculate the key. here's the problem The problem is I get -ve floating point numbers. How can I get the mod 26 of them? For example, what's the value of (-11/121) mod 26?