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

Modular Equivalence

Prove that if a and b are integers such that a|b and b > 0, then (x mod b) mod a = x mod a for any x. Solution: As a|b, we have b = pa for some integer p. Let x mod b = r, then we have x = bq + r = apq + r for some integer q. Hence, we have x mod a…
0
votes
3 answers

Is modulus a periodic function?

Is taking a mod of something, like 12 mod 2 (which is 0), a periodic function? If not, what kind of function is it and can it be classified as such?
0
votes
2 answers

Reducing exponents mod n

Say I have 5^(52) mod 22 How do I reduce this? I know if 22 was a prime number, then I could simply I could simply reduce 5^(22) * 5^(22) * 5^(8) which would become 5^(8) mod 22 but that doesn't work in this case.
0
votes
2 answers

If $a \equiv b\mod n$ then what is $a^m \mod n$ in terms of $a,b,n,m$?

If $a \equiv b\mod n$ then $a^m \equiv x \mod n$. Please express $x$ in terms of $a,b,n,m$. Also please provide an explanation, if possible.
user71408
0
votes
1 answer

Finding Solutions of Equations in $\mathbb{Z}_5$

This one should be easy. Just want to make sure I'm doing the right thing. Find the solution of the following equations in $\mathbb{Z}_5$: a) $x + 4 = 0$ b) $3x = 1$
user127543
  • 3
  • 1
  • 3
0
votes
2 answers

Finding the decoding formula and decoding message

Find the decoding formula for the encoding formula $y=9x+10$ and use it to decode "KOMF" Please give me a clear explanation and step by step solutions. Thank you.
user127543
  • 3
  • 1
  • 3
0
votes
4 answers

how to determine the modulo rules?

I´m repeating some old math exercises and could`t remember the following modulo rule: I have to find the smallest natural $k>0$ $mod(3^k,7)=1$ the solution seems straight forward. But I dont remember why: $mod(3^1,7)=(3,7)=3$ $mod(3^2,7)=mod(3 \cdot…
Googme
  • 355
0
votes
2 answers

Finding invertible elements in $\mathbb{Z}/m\mathbb{Z}$

Can anyone show me how to find invertible elements in $\mathbb{Z}/m\mathbb{Z}$, $m$ is say $28$? Also I'm not very clear about what it mean by 'invertible element in $\mathbb{Z}/m\mathbb{Z}$'
Arch1tect
  • 139
0
votes
3 answers

Calculating 2 rightmost decimal digits of large number (modular exponentiation)

I'm asked to calculate 2 rightmost decimal digits of large number, e.g. 3^2005. The hint is to use some modular trick (probably Euler phi function). Can anyone show me how to reduce the exponent?
Arch1tect
  • 139
0
votes
2 answers

Confusion on how to find answer to $11^{-1}\mod 26$

I'm confused how to find solutions to questions like $11^{-1}\mod 26$ and others like these. The solution is $19$ but I don't understand how. $11^{-1}$ on its own is $\frac{1}{11}$. Thanks
orange
  • 363
0
votes
1 answer

Jacobi Symbol To Determine Quadratic Residue

I have an exam tomorrow and I have no idea how I would do this type of question and I'm pretty sure its coming up can someone please help me out by maybe doing one as an example and explaining what then done and why I'd really appreciate it
dunika
  • 433
0
votes
1 answer

Finding the generator

In the discrete log problem we have to find the exponent, which is a hard problem but what if instead we wanted to find $a$ (the generator). I couldn't find it if there is already a question about it. So, if we have: $$b = a^x \mod n$$ where $n$ is…
Rubenisme
  • 103
0
votes
1 answer

Modular Arithmetic with Indices

How would I find $x$ where $\displaystyle 10^{33} \equiv x (\mod 13)$? I have an exam coming up and I'm not sure how to do this. I am assuming this can be done without a calculator but if not could someone tell me otherwise? I'd really appreciate…
dunika
  • 433
0
votes
2 answers

different ways of calculating mod values

Calculate $$10^{(10^{10})} \pmod 7$$ With Fermat: $$10^6 \equiv 1 \pmod 7 \Rightarrow 10^{6t} \equiv 1 \pmod 7$$ $$ \begin{eqnarray*} 10 & \equiv & -4 \pmod6\\ 10^{10} & \equiv & (-4)^{10}=[(4)^2]^5=(-2)^5=-32 \equiv 4 \pmod6\\ 10^{10} & = &6t+4…
user59768
  • 105
0
votes
1 answer

Find $m$ such that $a^m \bmod c = x$ given $a^n \bmod b = x$

Given $$ a^n \bmod b = x,$$ how can we find $m$ such that $$a^m \bmod c = x?$$ Edit: Alternatively, since we know $a$, $c$, and $x$, how you can solve for $m$ directly? Thanks for your help!