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

Filter by
Sorted by
Tagged with
1
vote
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 ...
0
votes
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$. ...
0
votes
1answer
72 views

Bezout's Identity and inverse modulo proof (GCD) [duplicate]

So might be a dumb question and actually quite simple, but I managed to confuse myself, and I don't really want to be learning the wrong thing. So $a≡b\;(\bmod n)$ can be defined by $a-b=ln,$ $l\in\...
0
votes
0answers
15 views

counting integers in modular function

Given a set of n positive integers. Say A={ 3,4,6,7,8} We have to find a number of integers in set that follow this property. property { factorial(x) mod (x+1) = x } here 3 and 7 are those numbers. ...
-1
votes
1answer
70 views

Find all element of order 5 in $Z^*_{36}$ [duplicate]

I brute force the solution of order 5 in $Z^*_{36}$ by using the following $a^5 \equiv 1 \mod 36$ and I see that there is no solution for this. However, I don't quite know how to prove this. Can ...
1
vote
2answers
34 views

Find x, where $x^\text{n}\equiv\text{m}\space\left(\text{mod}\space\text{p}_1\cdot\text{p}_2\right)$

Well, I have the following equation: $$x^\text{n}\equiv\text{m}\space\left(\text{mod}\space\text{p}_1\cdot\text{p}_2\right)\space\Longleftrightarrow\space x=\dots\tag1$$ Where $\text{n}\in\mathbb{N}^...
0
votes
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.
0
votes
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 ...
0
votes
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$ ...
2
votes
0answers
25 views

Guaranteed prime solutions to congruence relations

Let $p_1, p_2. ...,p_{x-1}, p_x$ be all of the the prime numbers from $2$ upto some arbitrarily chosen prime number $p_x$. And consider the representation of a natural number $n$ in the form $(a_x, ...
0
votes
0answers
11 views

Relationship between cyclic convolution and modulo operation

Could anyone explain the relationship between cyclic convolution and modulo operation ? Note: The screenshot below is taken from Richard Blahut's book Fast algorithms for signal processing
0
votes
2answers
26 views

Define $f : \mathbb{Z}_p \to \mathbb{Z}_p$ by $f([x])=[ax],a\in\mathbb{Z},p\nmid a$. Prove that $f$ is 1-to-1 & onto

Let $p$ be prime and define $f : \mathbb{Z}_p \to \mathbb{Z}_p$ by $f([x])=[ax],a\in\mathbb{Z},p\nmid a$. Prove that $f$ is 1-to-1 and onto. The question is equivalent to proving that $f$ permutes ...
6
votes
2answers
119 views

Find the smallest prime divisor of $1^{60}+2^{60}+…+33^{60}$

Find the smallest prime divisor of $1^{60}+2^{60}+...+33^{60}$. I found a solution online, but I have a few questions: In the beginning, the solver claims that $S^n = \begin{cases}S &\text{if } (...
1
vote
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 ...
2
votes
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$?
0
votes
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...
0
votes
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, ...
0
votes
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?
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
5
votes
1answer
114 views

Solve discrete logarithm, $a^x = b \bmod 2^N$ by p-adic logarithm

I want to find the smallest solution, $x$, for $$a^x = b \bmod 2^N$$ by using p-adic logarithm. We suppose $a \bmod 4 =1$ and $b \bmod 4 = 1$. Another case can be solved easily or converted to $a, ...
0
votes
0answers
17 views

Find $a$ inverse modulo 30, $1\le a \le 30$. For each $a$ you find, find the inverse of each $a$ that have inverse modulo 30 [duplicate]

Find $a$ inverse modulo 30, $1\le a \le 30$. For each a you find, find the inverse of each a that have inverse modulo 30 a={1,7,11,13,17,19,23,29} They got a by the fact that relative primes are ...
1
vote
0answers
34 views

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 ...
0
votes
1answer
23 views

$a = \gcd(2^m - 1; 2^n - 1)$. Why $2^n ≡ 1$ (mod $a$) and $2^m ≡ 1$ (mod $a$)? [closed]

$a =\gcd(2^m - 1; 2^n - 1)$. Why $2^n ≡ 1$ (mod $a$) and $2^m ≡ 1$ (mod $a$)?
1
vote
4answers
59 views

How to prove $14^{11}\pmod {23}$ is same as $22 \pmod {23}$ [closed]

How do we simplify the exponent in: $$14^{11}\pmod {23} \rightarrow 22 \pmod {23} ?$$
1
vote
0answers
38 views

Is it possible to have the gcd of 2 polynomials be the same in all fields?

So I have the polynomials $f(x) = x^3+x^2+x$ and $g(x)=x^2+x+1$ We are told to find the $gcd$ of both these polynomials in $Q[x], Z/3Z[x], Z/5Z[x], Z/11Z[x]$ After applying the Euclidean algorithm, ...
0
votes
0answers
40 views

Existence of only ONE solution to this modulo

I have to proof: If (a, m) = 1, then $ax\equiv{b}\pmod{m}$ has ONE solution in $\mathbb{Z}/m\mathbb{Z}$. I did the following: We have: $ax\equiv{b}\pmod{m}$. It follows: $b = ax + nm$, with n ...
3
votes
3answers
99 views

Find all solutions in modular arithmetic

I need to find all solutions to: $$4x\equiv3\pmod7$$ I know the solutions are in ${0, 1, 2, 3, 4, 5, 6}$ and I got $x \equiv 6 \pmod7$ so my answer was 6 but I don't know if that's all the ...
1
vote
3answers
42 views

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 ...
0
votes
0answers
30 views

Inverting exponentiation modulo a prime

Suppose p is an odd prime, g is a primitive root of p, i < p is any integer, and $w(i) = g^i \bmod p = k$. Note that if $i \neq j$, then $w(i) \neq w(j)$, so the map is in principle invertible. ...
2
votes
1answer
41 views

How to solve this modulo equation using modulo properties?

Equation: $[3*(k \mod 4)] \mod 4 = 3$ It's relatively easy to check the equation for the possible values of $k \mod 4$. Is there a more elegant way to calculate the solution, for example by using ...
0
votes
3answers
37 views

If I have n+1 element, why is it true that there will always be at least two that are congruent, modulo n?

As above ^; this is baffling me, I understand the intuition behind how modulus' work but it would be awesome if someone could actually explain to me how this works. Thanks in advance!
3
votes
1answer
58 views

The proof of $(n+1)!(n+2)!$ divides $(2n+2)!$ for any positive integer $n$

Does $(n+1)!(n+2)!$ divide $(2n+2)!$ for any positive integer $n$? I tried to prove this when I was trying to prove the fact that ${P_n}^4$ divides $P_{2n}$ where $n$ is a positive integer, where $P_{...
3
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
4answers
56 views

Solve $x\equiv 1(mod5), x\equiv 2(mod6), x\equiv 3(mod7)$

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 ...
0
votes
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?
0
votes
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 ...
0
votes
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 ...
1
vote
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$ ...
0
votes
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}$
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
7
votes
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. \...