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

Solve mod equation, how?

Ok so how would I solve for $j$: $(e*j)\bmod z=1$ When $e$ and $z$ are known integers. I am at a loss with this without using trial and improvement. Is there a formula I could use?
2
votes
2 answers

Multiple of $7$ that has remainder $1,2,3$ divided by $2,3,4$ respectively

I want the multiple of $7$ that has remainder $1,2,3$ divided by $2,3,4$ respectively. Now I have had a search of similar questions, but I may have missed it since I am on a phone. This question should be trivial to me, but I am having trouble, so…
user142198
2
votes
0 answers

How to simplify expression with Fermat's little theorem

I don't quite understand how to reduce $(25^{74} + 53^{27})^{10}$ I thought I would reduce to $(4^{74} + 4^{27})^{10}$ and then $(4^{7*10 + 4} + 4^ {7*3 + 6})^{7*1 + 3}$ And then $(4^4 + 4^6)^3$ but that doesn't seem like what the answer got so…
1
vote
1 answer

Secret sharing: modular arithmetic

I have this problem of sharing a secret code $n\in\mathbb{Z}$ such that $0\le n\le250$ among five people. There are 5 people, each one of whom receives a secret number $s_i$, $1\le i\le 5$ such that $0\le s_i \le 250$. What is a good scheme that…
user12488
  • 425
1
vote
3 answers

Finding remainders using modulo

Determine the remainder of $2014^{2015} \cdot 2016^{2017} + 2018^{2019}$ divided by 13. I can't figure out how to manipulate the 2018 part to get it to some form of 13. Any suggestions?
blaze
  • 19
1
vote
2 answers

Show that $47$ divides $5^{23}+1$

Show that $47$ divides $5^{23}+1$. My attempt: Since $47$ is prime and $47$ does not divide $5$, by Fermat's Little Theorem, $5^{47-1} \equiv 1 \pmod {47}$ $5^{46} \equiv 1 \pmod {47}$ Now I noticed that $\mathbb{Z}_{47}$ was a field. So that…
Bobby
  • 775
1
vote
2 answers

Modular Inverse

Calculate the Following $ (2^{19808}+6)^{-1} +1$ Mod (11) I'm completely lost here for several reasons. First of all the large power of 2 just throws me off and secondly I've seen inverse equations before never an inverse + a number. Could someone…
user145003
1
vote
1 answer

Calculus showing with mods

I got this problem from my Calculus II teacher, I have no idea how to approach it... Show that if $a,b,c$, and $d$ are integers such that $a\equiv b\pmod m$ and $c\equiv d\pmod m$, then $a+c\equiv b+d\pmod m$ and $ac\equiv bd\pmod m$. If anyone…
KFC
  • 1,185
  • 6
  • 21
1
vote
1 answer

Can the following modular equation be simplified?

The following equation is used to find the inverse of the remainder. Suppose we have a whole number w, which is divided by a natural number n. We assume that the remainder is r. Then the inverse i is defined as: i = (n - (w % n)) % n [equation 1] i…
1
vote
3 answers

How to simplify this alternating modulo expression?

The value of $(1000^i \mod 7)$ alternates between 1 and 6, as such: $$ 1000^0 \mod 7 = 1 $$ $$ 1000^1 \mod 7 = 6 $$ $$ 1000^2 \mod 7 = 1 $$ $$ 1000^3 \mod 7 = 6 $$ But as $i$ grows larger, these expressions can no longer be calculated easily by…
jayelm
  • 240
1
vote
3 answers

Modular Arithmetic: using congruence to find remainder

How do I use the fact that if $a = b \pmod n$ and $c = d\pmod n$ then $ac = bd\pmod n$ to find the remainder when $3^{11}$ is divided by $7$?
Daniel
  • 61
1
vote
3 answers

How do I find the modular inverse of $5^\space mod \space 26$?

I used the following formula to answer the question; $$\frac{((x∗k)+1)}{n},$$ where $x=(1,2,3...N)$. If the result of the formula is an integer then that result is the inverse to n mod k. In this case n=5 and k=26. So I found that when $x=1$ the…
1
vote
4 answers

Modular Arithmetic Simple question

Hi I am studying modular arithmetic just for myself, but to be honest I find it very difficult. I am not sure which answer is right. Is it right to say If $4x \equiv 8\pmod{15}$ then $x \equiv 2 \pmod{15}$ or just $x=2$ ? Thank you
moony
  • 720
1
vote
4 answers

Calculate $85^{2014}\bmod {82}$

Calculate the following equation $$85^{2014}\equiv x \bmod {82}$$ Answer is 73 in Wolphram Alpha, but I always lose myself doing the step by step
1
vote
0 answers

Higher residuosity problem, but with a known factorization

Given two large primes $p$ and $q$, two arbitrary odd integers $a$ and $b$, $x \in Z_{n^2}^*$ where $n$ = $pq$, find whether there exists numbers $c$ and $d$ that are distinct elements in $Z_{n^2} \setminus \{0,1\}$ such that $x = c^a.d^b \mod…
Misty