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

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.
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 ...
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$ ...
25 views

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 ...
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$?
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...
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, ...
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?
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 ...
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 ...
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 ...
114 views

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 ...
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 ...
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 ...
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 ...
56 views

Solve $x\equiv 1(mod5), x\equiv 2(mod6), x\equiv 3(mod7)$ First I can see $x=5t+1, t\in Z$. Then they insert this into the second equation, which is $5t+1\equiv 2(mod6)$, which leads to $t\equiv ... 0answers 52 views ### How can I find the numbers who are their own multiplicative inverse in mod m where m is not necessarily prime? Can I find the solutions, or number of solutions for $$a^2 \equiv 1\ (mod\ m)$$ where m is not necessarily prime? 2answers 44 views ### Get all linear congruences of$3x\equiv 6(mod9)$So to solve this I'm told that you find the gcd of 3 and 9, which is (3,9)=3 and since 3|6, there are 3 classes of solutions which can be found using the diophantine equation$3x+9y=6$. I was only ... 1answer 27 views ### prove that$[5, 7, 11, 13, 17, 19, 23]$are the only possible variants of the remainders (read context) when dividing the prime number$p$by 24 [duplicate] The problem is following: Given that$p$is a prime number,$p > 3$. Prove that$(p^2 - 1)$is divisible by$24$. I started writing down the possible remainders of dividing$p$by$24$and got ... 0answers 163 views ### Find integer$n$modulo composite. Suppose we want to find a positive integer$n < M$where$M$is a constant value of which we know a good approximation. For every prime$p$, an oracle gives us a set$B_p$of residuals modulo$p$... 3answers 60 views ### How to solve congruence system [closed] What is the step how can I solve following system of congruences (that is one system):$7x-8y≡5 \pmod {11}2x+5y≡9 \pmod {11}$1answer 93 views ### Prove that there are infinitely many primes congruent to 3 modulo 4 I know this question has been asked, but I think I finally have the right proof after looking at the others. I am just confused with one part of the proof. I am confused on the part where "Any two ... 1answer 67 views ### Help me find the pattern/idea of this I'm sorry for my bad english. English is not my main language. I've been trying to study this and its patterns for a while. You can see this in many ways, but the first way I saw this was from a ... 1answer 92 views ### Congruence with a Prime-power Modulus How would I go about computing: 5^11469 mod 1911? What I know: 1911 is not prime because it is divisible by 3. The same goes for the exponent 11469. Since both numbers are divisible by 3, can I ... 2answers 97 views ### How would I solve$53^{1069}$mod 54? [duplicate] I am doing practice problems for an upcoming exam and am wondering what approach I might take to solve$53^{1069}\$ mod 54. 1069 is a prime number, which means I can't factor the exponent. Some other ...
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. \...