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

Is there a way to solve congruences?

Ofter i come across things like this: $$7^x\equiv 1 \pmod{180} $$ $$x^3\equiv7 \pmod{13}$$ Are there easy ways to solve in general these kinds of congruences: $$a^x\equiv b \pmod{n} $$ $$x^a\equiv b \pmod{n}$$ For example $7^x\equiv 1 \pmod{180} $…
Kandinskij
  • 3,709
1
vote
1 answer

Solving linear equivalence mod $26$

I am looking to solve for $x$ in this modular arithmetic problem. We haven't learned anything remotely as complex as this in my class so not exactly sure where to start. $$y \equiv 5x + 25 \pmod{26}$$ Here's what I know so far. The additive inverse…
bla
  • 11
1
vote
3 answers

Using Fermat's Little Theorem or Euler's Theorem to find the Multiplicative Inverse -- Need some help understanding the solutions here.

The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm. a. $8^{-1}\bmod17=8^{17-2}\bmod17=8^{15}\bmod17=15\bmod17$ b. $5^{-1}\bmod23=5^{23-2}\bmod23=5^{21}\bmod23=14\bmod23$ c.…
1
vote
1 answer

Reducing powers modulos

Was working on a problem and reached this last part where I got an answer of $93^5 \bmod 95$. Anyone knows how to reduce $93^5 \bmod 95$ without using a calculator? Thanks!
1
vote
2 answers

Modular arithmetic: What does $\oplus$ mean in the context of $\mathbb{Z}_n$?

What do $\oplus$ and $\ominus$ mean in the context of modular arithmetic mod $n$, i.e. $\mathbb{Z}_n$? I'm familiar with using it as a bit-wise XOR operator, but in the context of mod $n$, this doesn't sound like it would make any sense. I am…
Addem
  • 5,656
1
vote
4 answers

Method to find solution for $a^x \equiv \mod n$

The congruence $5^x \equiv 1 \mod 36$ has a solution because $5$ and $36$ are relatively prime, i.e. $5$ and $2^23^2$ have no common factors. Is there a method to find $x$? All I can see is that $5^3 \equiv 5 \mod 6$.
1
vote
3 answers

Finding powers of 2 and 3 in modular arithmetic

Find all the powers of $2$ and $3$ modulo $17$. How would you solve this question and explain the steps please!
1
vote
3 answers

Proofs with Modulo Operation

I am still struggling with the modulo operation and have the following two to prove: Prove that for all $a_1$, $a_2$, $a_3$ $\in \mathbb N \cup${$0$} this applies: $$100\cdot a_3 + 10\cdot a_2 + a_1 = a_3 + a_2 + a_1 \bmod 3.$$ I used proof by…
Rikk
  • 101
1
vote
4 answers

Find the remainder when $99!+99$ is divided by $100$

Find the remainder when $99!+99$ is divided by $100$ I think I'm suppose to use either Wilson's or Fermat's theorem however, both 99 and 100 are not prime numbers so I can't use their formulas
Kayy Wang
  • 87
  • 5
1
vote
2 answers

Prove that $x+x^{3}+x^{5}+x^{7}+x^{9}+x^{11}\equiv 1\mod{11}$ has no solution

Prove that the following congruence has no solution on $\mathbb{Z}$ $$x+x^{3}+x^{5}+x^{7}+x^{9}+x^{11}\equiv 1\mod{11}$$ It is giving me hard times, some hints about it? Thank you
F.inc
  • 1,133
1
vote
2 answers

Finding a value mod M

I have the following expression: $X = 2^{(N+1)^2}-(N+1)^2-1$ And I want to find the value of X modulo M, where M < N and N is too large for me to just calculate X fully first. However, when I calculate this myself by applying the modulus…
user62753
  • 135
1
vote
0 answers

The last digit of $n!$ for $n \ge 5$ is always $0$. What are the options for the last non-zero digit of $n!, n\ge 5$?

I've found formulas online that use the greatest integer function, but they seem to answer my question for specific values of $n$. Is there an easier approach to find all values the last non-zero digit of a random $n$ can take? Is there another way…
MyWorld
  • 2,398
1
vote
1 answer

Solve $x^{18} \equiv 7^{99} - 7, \mod 592$

What I tried: $x^{18} \equiv 7^{99} - 7, \mod 592 \iff \begin{cases} x^{18} \equiv 7^{99}-7 & \mod 7 \\ x^{18} \equiv 7^{99}-7 & \mod 2 \\ x^{18} \equiv 7^{99}-7 & \mod 3\end{cases} \iff x^{18} \equiv 0, \mod 7,2,3. $ I'm not sure how to proceed:…
MyWorld
  • 2,398
1
vote
3 answers

For what values of n (where n is a natural number) is this statement true: $3^n - n - 1 ≡ 0\pmod5$

I'm clueless as where to start with this, $3^n$ seems to be of period 4, where $ - n - 1$ is of period 5.
1
vote
0 answers

Modular inverse of a fraction vs just the numerator

I found an unintuitive result, and I'd like help understanding why this is the case. I was experimenting with the sequence given by $a_n = 1 + \frac{1}{a_{n-1}}, a_1 = 1$. This sequence goes like $1, 2, \frac{3}{2}, \frac{5}{3}, \frac{8}{5},…
johnrolfe
  • 21
  • 2