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

How do I prove the following for the given congruence

If I have prime($x$) s.t, $x\equiv 5\mod 8$, How can I prove that $$xa^2 + 6b^2 \equiv 1 \mod 3x $$ has no solutions? I know this will involve Legendre somehow but since $8$ is not an odd prime I don't know how to proceed further
0
votes
1 answer

Why $ a^n\bmod\ m = a^{n\bmod (m-1)}\bmod m $ is true when $m$ is a prime number?

I know from Fermat's little theorem that $a^{m-1}\bmod m \equiv 1\pmod m $ when $m$ is prime number. But I don't understand how we got $ a^n\bmod m = a^{n\bmod (m-1)}\bmod m $ from Fermat's little theorem when $m$ is a prime number.
Ryzer
  • 3
0
votes
0 answers

modulo between two products of prime factor

$(a_1^{b_1} \cdot a_2^{b_2} \cdots a_n^{b_n}) \;\; \text{mod} \;\; (c_1^{d_1} \cdot c_2^{d_2} \cdots c_m^{d_m})$ Would there be a way to find the modulo (preferably in the form of a prime number product; or the worst case value). I am not allowed to…
0
votes
1 answer

Find all integers n such as $7^{n+1}-(n+1)7^n-1 = 0[4]$

Find all integers n such as $7^{n+1}-(n+1)7^n-1 = 0[4]$ we know that $ 7^2=1[4]$ But I don't know how to continue from here! I tried the fact that $7=7= -1 [4]$ $7^{2k} = 1 [4]$ $7^{2k+1} = -1 [4]$ The order is 2, I get when considering $n=2k$…
0
votes
0 answers

Calculate huge number mod $p$

How to calculate $n\bmod p$ when $p$ is prime, and $n$ is an integer of form $a9999...$ where $a$ is digit $1$ to $9$. The number of digits $9$ that follow $a$ is huge (i.e. big enough to not fit memory of my PC).
0
votes
2 answers

Prove that $3^{500} + 5$ is divisible by $14$ using theory of congruences.

Number theory question, based on the theory of congruences.
user909405
0
votes
3 answers

How to solve $ x * 23 \equiv_{60} 1 $ with $x \in \mathbb{N}$ and $ x > 100$

Can somebody help me how to solve $x* 23 \equiv_{60} 1 $ with $ x \in \mathbb{N} $ and $x > 100$ What would be a good approach? I know that x = 107 would be a solution. However how can I find solutions and how to prove that there are no solutions,…
0
votes
0 answers

Use the multiplicative inverse of $\overline{b}$ modulo $p$ to prove that there exists $z\in\mathbb{Z}$ for which $z^2\equiv-2\bmod{p}$

We have a Diophanite equation $$x^2+2y^2=p.$$ Suppose $p$ is prime, and there exists a solution $(a,b)\in\mathbb{Z}\times\mathbb{Z}$ to the Diophanite equation. Prove that there exists $z\in\mathbb{Z}$ for which $z^2\equiv-2\bmod{p}$. Hint: Show…
Hana
  • 57
0
votes
1 answer

Find all equivalence classes of $ab\equiv (0 \mod 5)$ for $a$ and $b$ modulo 5

I was asked to find all possible equivalence classes of $ab\equiv (0 \mod 5)$ for $a$ and $b$ modulo 5. If my understandings to this question is correct, there would be lots of work since we need to consider all possible permutations of…
Zen
  • 21
0
votes
1 answer

Square modulus question

"If $p ≡ 1 \pmod 4$ or $q ≡ 1 \pmod 4$, $p$ is a square $\pmod q$ iff $q$ is a square $\pmod p.$ What does "square mod q" means? I can't understand this statement.
0
votes
1 answer

Prove that if $3|a^2+b^2\Rightarrow 3|a ,\, 3|b$

How do i prove that if $$3|a^2+b^2\Rightarrow 3|a ,\, 3|b \,?$$ The book (Problem-Solving Strategies by Arthur Engels, page 43, E9) does not prove this theorem and leaves it as an excercise. I'm relatively new to this kind of problems and I just…
0
votes
1 answer

Prove a modular equation

If $a\equiv 1 \pmod n$ and $d\mid n$, then $a\equiv1 \pmod d$ is true. That is the question I am trying to understand so I have some understanding of the question but cant place my finger on exactly why it is true. $n = d \times k$ for…
zellez11
  • 287
0
votes
1 answer

Using modular arithmetic to find the remainder of $12^{157}$ when divided by $10$

So, I've figured out that: $12 \equiv 2 \mod 10$ And hence, $$ 12^{157} \equiv 2^{157} \mod 10$$ I thought of expanding out $2^{157} = 2^{156} \cdot 2 = 4^{78} \cdot 2 = 16^{39} \cdot 2$, then I could write: $$ 12^{157} \equiv 2^{157} \equiv…
0
votes
3 answers

Show that $ab \mod m = ((a \bmod m)(b \bmod m)) \bmod m.$

With modular definition in mind that two integers $a,b \in \mathbb{Z}$, are congruent module $m$ meaning that $a\equiv b \pmod{m}$, where $m$ is a positive integer. Details: $x \equiv y \pmod{m}$ is by definition equivalent to $m|(x−y)$. $x \equiv…
Avv
  • 1,159
0
votes
1 answer

Find all of the solutions of $4(x,y) = (1,2)$

Find all of the solutions of $4(x,y) = (1,2)$ in $\mathbb{Z}_3$ x $\mathbb{Z}_8$. What I have so far: $4(x,y) = (1,2) \implies (4x,4y) = (1,2) \implies 4x = 1 \pmod 3$ and $4y = 2 \pmod 8$.
user773349