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
-2
votes
1answer
21 views

Prove that the only solution to each of the following equations is (0,0)

Prove that the only solution to each of the following equations is (0,0): $n^2=5m^2$ $n^3=40m^3$ Thank you!
0
votes
0answers
26 views

Congruence $\text{mod } n$ : exponential property [duplicate]

Besides the exponent being a positive integer, are there any other restrictions to the exponential property of congruence modulus $n$: $a^k $ congruent to $b^k \text{ mod } n$, if $a$ congruent to $b \...
-2
votes
1answer
43 views

How to find modulo value?

How to find a modulo if the remainder is not coming? modulo =>is the remainder when one integer is divided by another For 7%5 = 7/5=1.4, modulo= 2. 2%5 =2/5=0.4, modulo=2
1
vote
0answers
33 views

Let $p$ be prime. Show that $[n^{p-1}]=[1]$ in $\mathbb{Z}/p\mathbb{Z}$ for all $1\leq n\leq p-1$.

I have the following Exercise. Let $p$ be a prime number. Show that $[n^{p-1}]=[1]$ in $\mathbb{Z}/p\mathbb{Z}$ for all $1\leq n\leq p-1$. Hint: Note that $(\mathbb{Z}/p\mathbb{Z})^\times=(\mathbb{Z}/...
1
vote
2answers
62 views

If n is not congruent to 2 modulo 4, then $ n=a^2 - b^2 $, with a, b integers.

This is the problem 5.54 in Childs - A concrete introduction to higher algebra. I found a proof of the inverse proposition, $ n=a^2 - b^2 $ then n is not congruent to 2 modulo 4,considering the ...
2
votes
1answer
70 views

Showing that it is not possible that for every $q_j$ it holds that $2+\prod_{k \neq j} q_k $ is divisible by $q_j$.

Let $n\ge 1$ and let $Q= \{q_1,\cdot\cdot, q_n\}$ be a set of $n$ primes, all different and larger than $3$. Show that there is no set $Q$ such that for every $q_j$ it holds that $2+\prod_{k \neq j} ...
0
votes
1answer
102 views

Let $m\in\Bbb N$. If $m$ is not prime, prove $\{1,2,...,m-1\}$ does not form a group under modulo-$m$ multiplication. [closed]

Let $m$ be a positive integer. If $m$ is not prime, prove that the set $\{1,2,...,m-1\}$ does not form a group under modulo-$m$ multiplication. I know I can use the axioms of a group to prove this. ...
-1
votes
0answers
42 views

Modular Multiplicative Inverse in Calculator [closed]

How do we calculate the multiplicative inverse of a number using a calculator? For example 7^-1 (mod 40)? Thanks in advance.
2
votes
1answer
44 views

Finding primitive roots modulo n code

I'm trying to translate some code into another language but struggling to understand the math behind it. The code is from this answer and is as follows: ...
2
votes
0answers
66 views

What is the meaning of $ \mathbb{Z}/m\mathbb{Z} $?

I'd like to know more about the meaning of the set: $$ \mathbb{Z}/m\mathbb{Z} $$I understand that it is the set of all equivalence classes of $$ [r]_m, r \leq m, \in \mathbb{Z} $$ What I don't ...
1
vote
0answers
156 views
+50

Proper divisors of $P(x)$ congruent to 1 modulo $x$

Let $P(x) $ be a polynomial of degree $n\ge 4$ with integer coefficients and constant term equal to $1$. I am interested in Polynomials $P(x) $ such that for a fixed positive integer $b$, there are ...
1
vote
1answer
29 views

Is there a formula for $|H_n|$, where $H_n = \{ $ units $u \pmod n$ such that $u^n = u, \}$ is the group of $(n-1)$th roots of unity modulo $n$?

Denote the group of solutions $X$ modulo $n$ to $$ X^{m} = X \pmod n $$ by $H(m,n)$. Then $H(m,n)$ is a subgroup of $G_n = \Bbb{Z}_{n}^{\times}$ the group of units modulo $n$. Note that $H(n-1,n) = ...
0
votes
3answers
37 views

Proving any two elements in recursive sequence are coprime.

A sequence $x_0, x_1, x_2, \ldots$ is defined recursively as follows: $$x_0 = 3 \\ x_n = 2 + (x_0 \cdot x_1\cdot x_2\cdots x_{n-1})$$ I'm stuck at trying to prove that for any two different elements ...
-3
votes
0answers
27 views

$aRb$ if and only if b-a is divisible by both p and q. Prove that the set of all equivalence classes of R is equal to Zpq. [duplicate]

I am stuck with proving the following. I am given a relation 𝑎𝑅𝑏 a R b if and only if b-a (two integers) divide both p and q, with p and q being distinct primes. I have already proved that the ...
1
vote
2answers
43 views

Counting solutions to $x^2+y^2 \equiv d \pmod{p}$ for a prime $p \equiv 3 \pmod 4$

For any given $p \equiv 3 \pmod{4}$ and $d=1, 2, \dots, p-1$, we would like to show that there are always exactly $p+1$ solutions to $x^2 + y^2 \equiv d \pmod{p}$. This conjecture comes from some ...
-1
votes
0answers
48 views

aRb if b-a is divisible by both p and q. Prove that the set of all equivalence classes is equal to $\mathbb{Z}_{pq}$

I'm stuck with proving the following. I am given a relation $aRb$ if and only if b-a (two integers) is divisible by both p and q, with p and q being distinct primes. I have already proved that the ...
5
votes
0answers
68 views

Proving that $\Sigma_{i=0}^{n-1} \alpha^i = 0$ for $k\mid n$ and $\alpha$ of order $k$

I've "found" the following theorem: If $n$ is a composite number, $k$ is a divisor of $n$, and $\alpha$ an element of $(\mathbb Z/n)^\times$ of order $k$, then $$\sum_{i=0}^{n-1} \alpha^i = ...
0
votes
0answers
76 views

If $x = 299269$, how do I show that $2^{x-1} \not\equiv 1 \mod x$ and deduce that $x$ is composite? [closed]

If $x = 299269$, how do I show that $2^{x-1} \not\equiv 1 \mod x$ and deduce that x is composite? Should I try finding the primitive roots and then approach the problem? I'm kinda stuck on how to ...
0
votes
2answers
51 views

$(x^3+x+1)^{-1} \mod (x^4+x+1)$ over $\text{GF}(2)$ [duplicate]

$(x^3+x+1)^{-1} \mod (x^4+x+1)$ over $\text{GF}(2)$ I understand well how to solve the equation without inverse but don't know how to solve it with inverse.
1
vote
1answer
21 views

For a finite (or countable) ring $R$, the matrices representing the group laws for $\cdot, +$ in $R$ have determinant $0$.

For example, the group law for $\Bbb{Z}/4$ is $A = \begin{pmatrix} 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 0 \\ 2 & 3 & 0 & 1 \\ 3 & 0 & 1 & 2\end{pmatrix}$. ...
2
votes
2answers
121 views

Solve: $x^2\equiv 1 \pmod{20},x^2\equiv 6 \pmod{15},x^2\equiv 9 \pmod{18}.$

I want to solve: $x^2\equiv 1 \pmod{20}, x^2\equiv 6 \pmod {15}, x^2\equiv 9\pmod{18}.$ This is a system of congruence equations, but these are not linear and moduli are not coprime. So,we cannot ...
0
votes
0answers
30 views

Solve equation with modulo for $b$?

I have the equation $(ax + b) \mod p = q$. I wish to solve this for $b$. I was thinking that since $(ax + b) \mod p = (ax + b) - \lfloor \frac{(ax + b)}{p} \rfloor p$, it would make sense if you could ...
2
votes
1answer
52 views

Reference on Heegner points

I am a senior undergraduate. I have learned something about elliptic curves (GTM97, GTM106, and the first few chapters of GTM151), modular forms (GTM228, Shimura's arithmetic theory of automorphic ...
1
vote
3answers
61 views

Find the element with the greatest order in the group $(\mathbb Z/2^{100}\mathbb Z)^*$. (Probably Lagrange theorem)

Find the element with the greatest order in the group $(\mathbb Z/2^{100}\mathbb Z)^*$. We know that $k$ divides $|G|$ (where $k$ is the order of any subgroup). Let's find $|G|$. We need to exclude ...
-2
votes
0answers
41 views

How to find all the solutions of this congruent equation? [closed]

I am thinking the following equation $$3^{84x}\equiv1+196\pmod{392}.$$ I do not know whether it has a solution.
0
votes
1answer
71 views

Show for $n>3$ satisfying this identity, that $n$ is not prime

While programming with prime numbers, I noticed the pattern that for $n>3$ satisfying this identity, then $n$ is not prime. Is that true? $$ \frac {(n-1)(n-2)}2 \equiv 1 \pmod{3} $$ Also, it seems ...
0
votes
0answers
32 views

Modular exponentation with 3 powers [closed]

In programming, if we have to do $$a^b \pmod{m},$$ we do modular exponentation. What if we want to do $$a^{b^c} \pmod{m},$$ and $b^c$ doesn't fit in the processor's word? Is there an adaptation?
1
vote
1answer
70 views

Show that $|\{\varphi\in \text{Aut}(\mathbb{Z}_{15})\mid \varphi=\varphi^{-1}\}|=4$

I want to show that there are exactly $4$ elements of the group $(\text{Aut}(\mathbb{Z}_{15}),\circ)$ with an order such that it divides $2$, that is, an element $\varphi\in\text{Aut}(\mathbb{Z}_{15})$...
1
vote
3answers
78 views

How is $\Bbb{Z}_2\otimes \Bbb{Z}_3$ isomorphic to $\Bbb{Z}_6$?

I am currently reading the book Group Theory in a Nutshell for Physicists by Anthony Zee and he wrote something about isomorphism I could not quite understand. Now we come in for a bit of a surprise....
-1
votes
1answer
59 views

Prove Erdos-Turan Theorem [closed]

Let $a_1 \lt a_2 \lt \dots$ be an increasing sequence of positive integers. Prove that for any $N$ we can find $i\ne j$ such that $a_i+a_j$ has a prime factor greater than $N$.
0
votes
1answer
35 views

What to do if the Extended Euclidean Algorithm terminates in one step?

I am trying to solve the linear congruence $14x \equiv 1 \pmod{113}$. So I first find $\gcd(14, 113) = 1$. However this means that: $113 = 14(8) + 1$ There is only one step needed. If I don't have ...
0
votes
0answers
27 views

How would I go about solving $11^{112114} \equiv x\pmod {113}$ [duplicate]

I'm studying for an exam, and this is one of the practice questions: For what number $x \in \{0, 1, 2, ... 112\}$ is the following statement true: $$11^{112114} \equiv x \pmod{113} $$ I have no ...
2
votes
0answers
83 views

How does this $\lfloor{\frac{qm[i] + \lfloor\frac{t+1}{2}\rfloor}{t}\rfloor}$ round up in case of a tie?

There is a code that is supposed to multiply a vector by $\lfloor q/t\rfloor$. It says this: ...
1
vote
0answers
42 views

Bézout's Identity vs. Fermat's Little Theorem for Finding Modular Multiplicative Inverses

While studying how to calculate the multiplicative inverse $a^{-1}$ of a number $a$ such that $a\cdot a^{-1} \equiv 1\mod p$, I found the majority of online resources immediately point to Bézout's ...
-1
votes
1answer
50 views

How do I find $9^{17} \bmod 7$ without a calculator [closed]

I've seen some examples of similar problems but I don't understand how they were solved. How would I solve $$ 9^{17} \bmod 7 $$ without calculator.
1
vote
1answer
44 views

What is the formula for going along a certain fraction of the circumference of a circle?

Say we have a circle with radius $1$, centered at the origin. If we want to start at the top of the circle and go clockwise along a certain proportion of the circumference, is there a formula for the $...
1
vote
2answers
58 views

Prove that $Γ(N)$ is a normal subgroup of $\mathrm{SL}_2 ( \mathbb Z )$

Consider the group of integral $2 × 2$-matrices of determinant $1$ $$ \mathrm{SL}_2( \mathbb Z) = \left\{M = \left( \begin{array}{cc} a \ \ b \\c \ \ d \end{array} \right)\Biggm| \ a,b,c,d \in \...
1
vote
1answer
50 views

Questions regarding the proof of the division algorithm

I have several questions regarding the following proof of the division algorithm. I added my question in brackets at the parts that I don't really understand. Thank you very much for your help! ...
2
votes
1answer
40 views

Show that $2^{2^n} = (\prod {p_i^{a_i}}\equiv 2^{n+1}\alpha_ix_i+1) \mod 2^{2n+2}\implies 2^{n+1} (x_1 \alpha_1 + \dots + x_k\alpha_k ) $

I had doubt in the following solution. However I couldn't understand the part " For this, it is enough to show that $x_i (\alpha_1 +\dots + \alpha_k ) \ge 2^{n+1}$" Then the author ...
0
votes
1answer
46 views

Is this function, $f$, a homomorphism under addition and subtraction?

Allow me to construct $f$ $\textbf{Lemma}$: For all $x \in [0,1]$, there exists a sequence $\{b_k\}_{k=1}^\infty$ such that $$\forall k \in \mathbb{N}, b_k \in \{0,1\}$$ And $$x = \sum_{k=1}^\infty \...
-3
votes
1answer
52 views

If $a$ is a unit, prove that $ax \equiv b (\bmod n)$ has a unique solution [closed]

The whole question is: If $a, b \in \mathbb Z/n \mathbb Z$ and $a$ is a unit, prove that $ax = b$ has a unique solution in $\mathbb Z/n\mathbb Z$. I know it has something to do with $au=1$ for some $u ...
0
votes
3answers
164 views

Small lemma on moving up multiplicative inverses of powers needs explanation

I am reading about a lemma that shows how to lift up a multiplicative inverse. I.e. if we know that $3\cdot 3 \equiv 1 \pmod {2^3}$ then we know that $3\cdot 43 \equiv \pmod {2^6}$ To go from $\pmod {...
0
votes
1answer
96 views

Is $\{0,1,3\}$ a proper subgroup of $\mathbb Z _ 4$ under addition?

Is $\{0,1,3\}$ a proper subgroup of $\mathbb Z _ 4$ under addition? I think it is not because closure property does not hold for it. If we check, $3+3$ gives $2$ (in $\bmod 4$) which is not present ...
1
vote
2answers
65 views

How to prove that $x + y \equiv 4\pmod 6 $

Prove that if x and y are integers such that $x \equiv 3 \pmod{12}$ and $y \equiv 7\pmod{18}$, then $x + y \equiv 4\pmod6$ I tried making the equations into algebraic equations. So, $x\equiv3\pmod{12}$...
4
votes
1answer
141 views

if $\mathrm{ord}_p(b)\mid \mathrm{ord}_p(a)$ for all sufficiently large prime p, is $b$ necessarily a power of $a$?

Let $a$ and $b$ be integers, and denote by ${\rm ord}_p(a)$ the $\textbf{multiplicative order}$ of $a$ modulo $p$. Assume that there exists a constant $K$ such that for all prime $p>K$, ${\rm ord}...
1
vote
1answer
60 views

Proof that $42\mid x_n$ for all $n\geq 1$.

I was given to prove that for $x_n = 7^n + (-6)^n -1$, then $42\mid x_n$ $\forall n\geq 1$. I know that working in $\bmod 42$ is the obvious choice here, but I initially thought that since $42= 2\cdot ...
0
votes
0answers
31 views

A $\bmod p$ version of the Frobenius coin problem.

Let $x_1,\dots,x_d$ be $d$ integers having greatest common divisor equal to $1$. By Bézout's Lemma, there exists a least $\kappa(x_1,\dots,x_d) \in \mathbb{N}$ such that any $k \geq \kappa(x_1,\dots,...
1
vote
1answer
58 views

Counting in mod

Arnold, Riaz and Topaz are counting from $1$ to $999$, Arnold, then Riaz and Topaz. For example: Arnold counts $1$, Riaz counts $2$, Topaz counts $3$, Arnold counts $4$, and until Topaz finally calls $...
0
votes
1answer
19 views

How to check if it is possible to reach every element in an array via jumps of length m (modulo N)?

Given an array of length N, starting from the first position, how to check if it is possible to reach every position if it is only possible to jump m units. EDIT: I just found that it depends on the ...
0
votes
2answers
85 views

Questions about 81st Putnam, Day 1 Question 1

I'm working through past Putnam questions and solutions and had some confusion about the 81st Putnam, Day 1, Question 1. Problems and Solutions The first problem reads as follows: Question And the ...

1
2 3 4 5
238