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

Finding the last digit of $103^{103^{103^{103^{103}}}}$

I need to find the last digit of $103^{103^{103^{103^{103}}}}$ so the value in $\mod10$. I know \begin{align} 103^{103^{103^{103^{103}}}}&=(100+3)^{103^{103^{103^{103}}}}\\ &=100\cdot(stuff)+3^{103^{103^{103^{103}}}}\\ &=3^{103^{103^{103^{103}}}}…
1
vote
1 answer

Finding the least significant bits in different bases

I have this number 1547882635 and I want to find the least significant bits of it in different bases. I know I can find it like for base4 I can turn the 2635 to base4 and take the 3 right most digits and it is the same digits as my main number. But…
1
vote
1 answer

$x \equiv y \bmod p$ implies $x^{p^{k-1}} \equiv y^{p^{k-1}} \bmod {p^k}$?

I am asking myself the following question: Let $p$ be a prime. Is it true that $x \equiv y \bmod p$ implies $x^{p^{k-1}} \equiv y^{p^{k-1}} \bmod {p^k}$? I can not see how to prove this, but I do not find a counter example either. Could you help…
3nondatur
  • 4,178
1
vote
2 answers

How to reduce a congruence to a "unique" solution?

I have to find a value for $r$ such that it is within the bounds of a modular equation. For example: $$2381\equiv r\mod{87}$$ So I need to find $0\leq r<87$. How can I do this? The notes I took in class are absolutely horrible so I can't find the…
Mirrana
  • 9,009
1
vote
1 answer

Fermat's Little Theorem when the exponent is less than the $p - 1$

F.L.T. tells us: $$a^{p-1} \equiv 1 \mod p$$ In all the cases I have seen, we are able to break down a larger exponent such that it will contain $a^{p-1}$. Like examples 1 - 7 here. But how would we handle an example where the exponent is smaller…
1
vote
3 answers

Solving for Congruence Class

I’m trying to solve the following problem: Find all solutions to [11][x]^46 + [45][x]^11 = [4] in Z55 with 0 <= x < 55. Can anyone please tell me how to solve this?
user720998
1
vote
0 answers

Is there a rule for converting a modulus in the form 2^n + 2^m to bit-wise &, and addition?

I have been playing around a little with trying to figure out a general rule for this but I suspect someone has already figured it out or at least there is some word for this kind of decomposition. $x \mod (2^n+2^m) = F(x,n,m)?$ For example if n=3,…
1
vote
2 answers

Proof by counter example: does it work?

Let $n \in \mathbb{N}_{\geq 2}$. Prove that the following statements are equivalent (1) For every $x \in \mathbb{Z}_n,$ if $x^2 \equiv 0,$ then $x \equiv 0.$ (2) There is no prime $p$ such that $p^2 | n.$ To prove (1) $\implies$ (2), I attempted…
1
vote
2 answers

Solving the congruence system and checking the answer

I have a congruence system to solve, that I actually tried to solve. The problem is that I'm not sure that I did it right, because at the end I cannot find a proper number that will be working fine for all of the equations.…
Mary
  • 25
1
vote
1 answer

Help in Modular Arithmetic

How do I simplify the following: $a^{b} \ \pmod {b}$ where $b$ is very large. For example: $2^{499} \pmod {999}$ How do I find the result without computing all? I don't want to use such a quantity of memory for storing the value of $2^{499}$. Is…
1
vote
0 answers

How did this word problem related to linear congruences get $11x=17(mod24)$

So if the first sentence is gone I'd intuitively get that it'd be $11x=17(mod24)$, but I think the first sentence regarding that it's an exact multiple of 1 hour that is less than 1 day is relevant to this.
Gooby
  • 497
1
vote
3 answers

Which of $[0]_3, [1]_3, [2]_3$ is $[5^k]_3$ equal to?

Let $k\in \mathbb{N}$. Which of $[0]_3, [1]_3, [2]_3$ is $[5^k]_3$ equal to? Prove your answer. Below is my proof so far. I figured out what it equals when $k$ is even or odd, which is hopefully correct. And I know from this then a case for both…
A.A.
  • 361
1
vote
1 answer

Some integer does not have a square root in $\mathbb{Z}_n$ if $n \geq 3$.

Some integer does not have a square root in $\mathbb{Z}_n$ if $n \geq 3$. I am having difficulty showing this. Can someone provide minimal guidance, or a small hint to point me in the right direction?
1
vote
4 answers

Finding all integers $k \geq 2$ such that $k^2 \equiv 5k \pmod{15}$. What is going on here?

The question is as follows: Find all integers $k \geq 2$ such that $k^2 \equiv 5k \pmod{15}$. I have an issue related to this question (its not about the solution to the question): I know that $\overline{k} \in \mathbb{Z}_{15}$ is invertible if…
1
vote
1 answer

Modular arithmetic proof

If $a\equiv b \pmod {m_i}$, $1\leq i\leq k$, there $m_1,m_2,\dots,m_k$ relatively prime, then $a\equiv b\pmod{m_1m_2\cdots m_k}$ My attempt: $$\frac{a-b}{m_i}=t_i, t_i\in Z$$ $$\frac{(a-b)^k}{m_1m_2\cdots m_k}=t_1t_2\cdots t_k$$ $$(a-b)^k\equiv 0…
user1242967
  • 1,727