The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
0
votes
0answers
13 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
28 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\...
5
votes
4answers
87 views

Prove that $x^3+2y^3+4z^3\equiv6xyz \pmod{7} \Rightarrow x\equiv y\equiv z\equiv 0 \pmod{7}$

Wants: $x^3+2y^3+4z^3\equiv6xyz \pmod{7} \Rightarrow x\equiv y\equiv z\equiv 0 \pmod{7}$ My attempt: With modular arithmetic, I can show that if $x\not\equiv0$, then $y\not\equiv0$, and $z\not\equiv0$...
0
votes
0answers
12 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. ...
2
votes
0answers
17 views

Any index formula $f(x_n)=n$ for element in series $x_{i+1} = ax_i^{-1}+b \mod P$? (inversive congruential generator)

$$x_{i+1} = ax_i^{-1}+b \mod P$$ $x_0, a,b$ and prime $P$ are given. The values for $a,b$ are chosen to maximize the period length which is equal to $P$. This equation is used in the inversive ...
-1
votes
4answers
55 views

What integers can be reduced fraction $\frac{5k + 6}{3k + 1}$? [on hold]

What integers can be reduced fraction $\frac{5k + 6}{3k + 1}$? $k$ is an integer. I've tried to substitute some numbers and i assume the answer is (-infinity; 2]. If it's right, how to prove it?
0
votes
1answer
35 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
33 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
42 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
12 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
13 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
21 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
8 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
25 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
101 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
34 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
54 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
34 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
39 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
23 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?
0
votes
1answer
37 views

Find the exponent with which $5$ is among the $1000!$

Find the exponent with which $5$ is among the $1000!$ I'm not sure where to start again. Give me a hint maybe?
-1
votes
1answer
16 views

Congruent Prime Modulos [on hold]

Why given p,q are distinct primes, $a^k \equiv 1 \pmod{p}$, and $a^k \equiv 1 \pmod{q}$, then $a^k \equiv 1 \pmod{pq}$?
1
vote
2answers
43 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
37 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 ...
1
vote
3answers
44 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 ...
-1
votes
1answer
24 views

Show binomial congruences modulo 2,3,4 [on hold]

I need to show that for integers $x$ and $y$, $$(x+y)^2 \equiv x^2 + y^2 \mod 2,$$ $$(x+y)^3 \equiv x^2 + y ^2 \mod 3,$$ and $$(x+y)^4 \not\equiv x^4 + y^4 \mod 4.$$ How do I go about this?
4
votes
1answer
95 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
16 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
32 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
20 views

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

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

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

How do we simplify the exponent in: $$14^{11}\pmod {23} \rightarrow 22 \pmod {23} ?$$
1
vote
0answers
35 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
90 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
38 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
26 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. ...
0
votes
0answers
26 views

prove that the number *pic related* is an exact square [duplicate]

Prove that the number $$\underbrace{4...4}_{n}\underbrace{8...8}_{n-1}9$$ is an exact square. I'm not really sure where to start even.
2
votes
1answer
36 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
31 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
46 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_{...
1
vote
5answers
129 views

prove that $(n^2 +5n + 16)$ is not divisible by $169$

Prove that $(n^2 + 5n + 16)$ is not divisible by $169$ for any integer $n$. Iterating all the remainders looks too difficult but what can i do then?
0
votes
0answers
32 views

Observed that $\sum_{k=1}^{n-1}k^n\equiv n/2\pmod{n}$ if $n$ is even but not a multiple of 6 and $n/6$ if $n$ is a multiple of 6 [closed]

I have already proved the case that $\sum_{k=1}^{n-1}k^n\equiv 0\pmod{n}$ if $n$ is odd. For the case where $n$ is even I am stuck at the expression $$ 2(1^{2m}+\cdots+(m-1)^{2m}) +m^{2m}\pmod{2m} $$ ...
0
votes
4answers
67 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
39 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
50 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
47 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
42 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 ...
-3
votes
0answers
34 views

Proofs in Mod P [duplicate]

I have two questions I am very stuck on and would appreciate some help. Suppose that $p$ is a prime with $p ≡ 3 (mod 4)$. Show that for all $x \in \Bbb Z_p (mod p)$, it is not possible for both $x$...
0
votes
1answer
26 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
126 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$ ...