# 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$.

9,929 questions
Filter by
Sorted by
Tagged with
4answers
35 views

### How do I find the remainder for the following?

I know this is a very typical question for modular arithmetic but still I haven't found a comprehensive explanation for this question, so I'm posting it here. So here goes: I need to find the ...
0answers
32 views

### Exponentiation of a modulo sum

Suppose a finite field in $F_p$, $p$ being a large prime and $g$ a generator of the field. Let two parts $A$ and $B$,with $A$ knowing a secret $a \in F_p$ and $B$ knowing another secret $b \in F_p$. ...
1answer
72 views

2answers
66 views

### Prove that $n^4 + 2n^3 + 2n^2 + 1$ is not an exact square.

Prove that $n^4 + 2n^3 + 2n^2 + 1$ is not an exact square for any natural $n$. Sorry i know it's a very simple problem but i can't find a right way to prove it.
1answer
15 views

### Lemma of the Primitive Root theorem

Let's take a primitive root $g$ for a prime $p$. Then if $j$ and $k$ are integers, then $g^{k}\equiv g^{j} \quad mod \,p$ only if $k \equiv > j \quad mod \, p-1$ Is it possible to understand ...
0answers
17 views

### Primitive root in modular arithmetic

Let's take a prime number $p$ and a number $a$ that is not a primitive root modulo $p$. It has been proved that there exist at least a number $b \quad mod \, p$ for which is impossible to find a $x$ ...
0answers
25 views

2answers
37 views

### 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 ...
1answer
68 views

### Number of subgroups of $\mathbb Z _m \times \mathbb Z_n$

Let $\mathbb Z_m$ denote the additive group of residue classes modulo $m$. Is there a closed form for the number of subgroups of $\mathbb Z_m\times\mathbb Z_n$?
0answers
38 views

### How to solve a system of $2$ linear equations modulo n for $3$ variable?

$$2x + 2y - z = 2\pmod {3}$$ $$-x - 4y - 2z= 4\pmod {3}$$ I am lost in this... For simple equations I used Euclidean Algorithm. But in this problem I dont really know how to use this algorithm...
1answer
44 views

### Find the remainder when $10^{20^{30}}$ is divided by $23$ [duplicate]

Find the remainder when $10^{20^{30}}$ is divided by $23$ I guess this question is fairly simple, but I just want to make sure I'm on the right track. My answer is shown below. If it is incorrect, ...
2answers
24 views

### Can a number consisting only of numbers $8$ and $6$ be a square of an integer?

Can a number consisting only of numbers $8$ and $6$ be a square of an integer? I'm confused. Which approach can be used in solving this?
2answers
121 views

### simultaneous linear congruence- Chinese remainder theorem

find a integer r that satisfies both congruence r ≡ 3 mod 1293 and r ≡ 0 mod 3936 im stuck on this question my method was using Chinese remainder theorem. first found the gcd(1293,3936) = 3 then ...
1answer
38 views

### Help in Modular Arithmetic [duplicate]

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 ...
3answers
48 views

### Find gcd($2^{19} + 1$; $2^{86} + 1$)

Find gcd($2^{19} + 1$; $2^{86} + 1$) It would be easy to give a formal proof for any gcd($2^{n} + 1$; $2^{m} + 1$) based on Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$ if $m$, $n$ were ...
1answer
114 views

5answers
274 views

### How does one prove that $n^2 +5n + 16$ is not divisible by $169$ for any integer $n$?

How does one prove that $n^2 +5n + 16$ is not divisible by $169$ for any integer $n$? THOUGHTS: This is equivalent to say that $$n^2 +5n + 16=0\pmod{169}$$ has no solutions. One can also observe ...
1answer
34 views

### Runtime of modular expansion

I understand nearly everything about cryptology, but runtime and bit operations. I have following problem: How many bit operations are necessary to calculate a^n mod m for constant m and a. I have ...
4answers
80 views

### Solve $x\equiv 1(\mod2)$, $x\equiv 2(\mod3)$, $x\equiv 3(\mod4)$, $x\equiv 4(\mod5)$, $x\equiv 5(\mod6)$ and $x\equiv 0(\mod7)$

$$x\equiv 1(\bmod2)$$ $$x\equiv 2(\bmod3)$$ $$x\equiv 3(\bmod4)$$ $$x\equiv 4(\bmod5)$$ $$x\equiv 5(\bmod6)$$ $$x\equiv 0(\bmod7)$$ So the solution says we can eliminate $x\equiv 5(\bmod6)$ because ...
3answers
42 views

### Solve $x\equiv 1\bmod2, x \equiv 1\bmod5$ and $x \equiv 0\bmod3$

$$x\equiv 1\mod2\\ x \equiv 1\mod5\\x \equiv 0\mod3$$ Somehow I got the wrong solution Here's how I got them $b_i$ | $N_i$ | inverse| Product 2 | 20 | 4 |160 2 | 12 | 3 | 72 0 | 15 | 3 | 0 ...
4answers
56 views

0answers
6 views

### Solution of straight line inequality with zero gradient sections?

Is there a closed form solution for a straight line inequality in the integer domain, in the modified problem where the line is formed of sections of non-zero gradient straight lines, interspersed ...
3answers
413 views

### Euclid Algorithm to Find Muliplicative Inverse

Here I am trying to find the multiplicative inverse of 19 respect to 29. $$19x \equiv 1 \pmod{29}$$ What I tried \begin{align*} 29 &= 1(19) + 10\\\ 19 &= 1(10) + 9\\\ 10 &= 1(9) + 1. \...