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
4 answers

Find the least significant digit

Explain why the number $(3^{27}\cdot7^{313}\cdot11^{121})^{1000}$ has 1 as its least significant digit. I know I am supposed to use $\pmod{10}$ but I am not sure how to combine the answers of the individual powers and then raise them to $1000$
1
vote
3 answers

How one can deduce that $tx≡2t[mod(z)]$?

Let $x,y,z,t$ four positive integers. If $$x≡2[mod(y)]$$ and $$z=ty$$ Then how one can deduce that $$tx≡2t[mod(z)]$$
DER
  • 3,011
1
vote
1 answer

How to prove integers has a cubic root mod p?

Using p ≡ -1 (mod 3) and p is prime, how can you show $a^3≡b$ (mod p) iff $a≡b^d$ (mod p)? This shows integers mod p has a unique cubic root. 3d ≡ 1 (mod p-1) I'm not sure where to begin... Does anyone know? Thanks
omega
  • 751
1
vote
6 answers

How to solve this equation if we can't use Chinese remainder theorem.

Let consider: $$\begin{cases}6x \equiv 2 \mod 8\\ 5x \equiv 5\mod 6 \end{cases}$$ We can't use Chinese remainder theorem because $\gcd(8,6) = 2 > 1$ Help me.
user180834
  • 1,453
1
vote
2 answers

Modular arithmetic with (mod 20)

Got a question on my midterm in discrete mathematics and I can' figure out how to approach it: $19^{3701}+1 \equiv 0\ (\textrm{mod}\ 20)$ I was thinking about Fermat´s little theorem, but the 20 is not a prime ...
1
vote
1 answer

Why is the discrete logarithm problem in $(\mathbb{Z}_n,+)$ easy?

I have trouble understanding why the discrete logarithm problem in $(\mathbb{Z}_n,+)$ should be easy: I tried it with the following example: $$a \cdot b \equiv y \pmod {p}$$ If $a=11, b=2$ and $p=19$: $$11 \cdot 2 \equiv 3 \pmod {19}$$ If someone…
libjup
  • 313
1
vote
2 answers

Principal Square Root mod

"Theorem: let p be a prime satisfying $p=3\bmod4$. Then for an integer y which is a square modulo p, $x=y^{(p+1)/4}\bmod p$ is a square root mod p of y. That is, $x^2=y\bmod p$. This is called the principal square root of $y$. I don't know really…
Math Major
  • 2,234
1
vote
6 answers

simple 'why' question about modular arithmetic 13 mod 5

After checking out khan academy "what is modular arithmetic" https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic they say that 13/5 = 2 remainder 3, and therefore 13 mod 5 = 3 but 13/5 = 2.6…
1
vote
3 answers

Question on modulo

Find the last two digits of $3^{2002}$. How should I approach this question using modulo? I obtained 09 as my answer however the given answer was 43. My method was as follows: $2002\:=\:8\cdot 250+2$ $3^{2002}=\:3^{8\cdot 250+2}\:=\:3^{8\cdot…
0
votes
1 answer

How to prove these statements : $3 \mid (10^{n+1} + 10^n + 1)$ and $(a-b) \mid (a^n - b^n)$

I was looking at some proof questions and had difficulty answering a few of them How do I prove these statements below: 1) $3 \mid (10^{n+1} + 10^n + 1)$ 2) $(a-b) \mid (a^n - b^n)$
gexcen
  • 19
0
votes
1 answer

Method to solve for a number in modulus equation.

If you had an equation of 12 = (8000 + B) mod 13 You could guess and check a little and arrive at B = 7. My question is what is the best way to solve these? Is there a defined method to get B?
0
votes
2 answers

Prove that if a $\in \mathbb{Z}$ then $a^{3} \equiv a(mod 3)$

Prove that if a $\in \mathbb{Z}$ then $a^{3} \equiv a(mod 3)$ So, the ways I have learned (or am learning, rather) to do proofs is using direct, contrapositive and contradiction. So, I started it using direct, and got this: $n|(a^{3}-a)$ Then there…
0
votes
1 answer

Integer solution for $174582x + 1818342y = 54$

How can I find an integer solution for $x$ and $y$ for this problem type? I think I have to find a modulo relation between $54, 174582$ and $1818342$, but I am clueless.
Guest
  • 1
0
votes
2 answers

Correct behaviour of mod operation compared to Google calculator

What is happening here? Why is the first calculation returning an integer, but not the second calculation? What are the rules for computing mod for floats and negative numbers?
0
votes
2 answers

Find a prime $p$ satisfying $p \equiv 1338 \mod 1115$

Find a prime $p$ satisfying $p \equiv 1338 \mod 1115$. Are there infinitely many such primes. A little confused about this problem, any help or advice?
Pasie15
  • 491