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$.
12,809
questions
3
votes
1
answer
55
views
Proof of statement with modular arithmetics
I have the following question:
Let $p$ and $q$ are distinct prime numbers. Let $a \in \mathbb{N}$ such that $p \nmid (a^{pq}-1)$ and $q \nmid (a^{pq}-1)$. Prove that $\exists$ prime number $r$ such ...
- 45.8k
1
vote
1
answer
33
views
Quadratic residues of low degree polynomials in $\mathbb{F}_p$
Let $(\frac{a}{p})$ denote the Legendre symbol. Let $P$ be a polynomial over $\mathbb{F}_p$ of degree $d$. I would like to upper bound
$$\Big\lvert\,\mathbb{E}_a \Big(\frac{P(a)}{p}\Big)\Big\rvert$$
...
- 8,022
0
votes
1
answer
45
views
For $n$ houses arranged in a circle, a man goes clockwise skipping $i$ houses every time. For what value of $n$ does he visit each house? [duplicate]
A man wants to visit every house a circular road with $n$ houses. For this he starts at a house and then moves clockwise, always skipping exactly $i$ houses before stopping at the next house. For ...
- 318
0
votes
0
answers
58
views
Prove that there exists 5 consecutive numbers, each of which is divisible by a cube of a positive integer greater than 1. [duplicate]
I have trouble even starting on the question because I cannot create any relationships between those 5 numbers.
- 267k
2
votes
2
answers
123
views
Primes in a list formed by multiplying $5$ by $a$ and adding $b$
Take two positive integers $a$ and $b$ that are not multiples of $5.$ Then, construct a list in the following fashion: let the first term be $5,$ and starting with the second number, each number is ...
- 267k
2
votes
2
answers
287
views
$2^n$ modulo n where n is odd always yields either an even or $1$
I'm attempting to do a pidgeonhole proof to prove that for some odd integer n, there is always a $2^k$ such that $2^k \mod(n) = 1$. I know that $2^n \mod(n)$ will always yield either an even number or ...
- 267k
0
votes
0
answers
50
views
How to solve congruence like these? [duplicate]
So i have three weird congruence that i don't know how to start:
$2021^{2021}-2021^{101}≡? \quad (mod \quad 600)$
$46^{47^{48}}≡? \quad (mod \quad 25)$
$39^{1200}≡? \quad (mod \quad 26)$
I know ...
- 267k
2
votes
0
answers
169
views
+500
Sum of even binomial coefficients modulo $p$, without complex numbers
Let $p$ be a prime where $-1$ is not a quadratic residue, (no solutions to $m^2 = -1$ in $p$).
I want to find an easily computable expression for
$$\sum_{k=0}^n {n \choose 2k} (-x)^k$$
modulo $p$. ...
- 4,182
0
votes
0
answers
23
views
what the condition for $P$ devided by $Q$. [duplicate]
We consider two polynomial $P(X) =X^{4n}+X^{3n}+X^{2n}+X^{n}+1$ and $Q(X) =X^{4}+X^{3}+X^{2}+X+1$ So what the condition for $P$ devided by $Q$.
we note $P(X)= Q(X) H(x)+ R(X)$ if $P$ devided by $Q$ ...
- 267k
-3
votes
0
answers
70
views
How Often do Complex Numbers Follow Fermat's Little Theorem? How can you predict them? [closed]
Essentially, for a gaussian integer $x$ where all dimensions' coordinates<$p$, how many $x$ given dimension $d$ and prime $p$ satisfy $y≡x$ (mod p)? Is there any way to predict these? Any upper ...
1
vote
2
answers
77
views
Finding cubic residues modulo $9$
I wish to find all cubic residues modulo $9$, i.e., all invertible classes $A$ modulo $9$
such that the congruence $X^3 \equiv_{9} A$ is solvable. I have so far determined that the invertible classes ...
- 267k
0
votes
0
answers
16
views
Dissection and congruences of the generating functions [closed]
From what I have seen so far, in integer partitions, the arithmetic study of any class of partitions uses the Modular forms, or the m-dissection of partition function.
For example: the famous ...
- 1
0
votes
0
answers
28
views
Final digit of $a[n]a$, where $[n]$ is the $n$-th hyperoperator and $a \in \mathbb{Z}^+$
While I was submitting a few sequences to the OEIS, I noticed an asymmetrical pattern involving the rightmost digits of an interesting set of well-known integer sequences.
Let $a \in \mathbb{Z}^+$, $n ...
- 267k
1
vote
4
answers
3k
views
How do you find the modular inverse of $5\pmod{\!11}$
I need to find out the modular inverse of 5(mod 11), I know the answer is 9 and got the following so far and don't understand how to than get the answer. I know how to get the answer for a larger one ...
- 267k
0
votes
0
answers
96
views
Eisenstein Integers modulo $(1-\omega)^2$
I wish to find the addition and multiplication tables of Eisenstein integers modulo $(1-\omega)^2 = -3\omega$. In drawing the fundamental parallelogram with vertices at $0, z = - 3\omega, z\omega = 3+...
- 267k
-2
votes
0
answers
29
views
Why is $(a^{p^{n-1}})^{p-1}=(a^{p^{n-1}(p-1)})\equiv_{p^n}1$ true when $p$ is a prime? [duplicate]
I am having some trouble to understand a step of the proof of proposition 3.6.27(c) from this book.
The proof states that if $p$ is an odd prime then there is a natural number $a$ such that $a^{p-1}\...
- 71
-1
votes
0
answers
75
views
Reducing $\,2^{\:\!p^2-1}\bmod p^2\,$ for $\,p = 1093$ [duplicate]
Find the least non-negative number a congruent to $2^{1194648} (mod 1194649)$. Could
1194649 be prime?
Currently, I have that $2^{1194648} = 2^22^22^22^32^72^{13}2^{547}$.
How could I continue.
Can ...
- 267k
14
votes
3
answers
776
views
Can we generalize the quadratic formula to modular arithmetic?
Does the quadratic formula $\displaystyle x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$ hold modulo $n$ for $ax^2 + bx + c \equiv 0 \pmod n$?
Computing the square root would require factoring $n$ and using ...
- 267k
0
votes
1
answer
64
views
Solving $x^2 + 7x \equiv 1\pmod{13}$ [duplicate]
How should I solve this particular congruence: $x^2 + 7x \equiv 1 \pmod{13}$?
I can re-arrange the equation to get $$x^2 + 7x - 1 \equiv_{13} 0$$. In noticing that $7 \equiv_{13} -6$, can I replace $...
- 267k
-3
votes
1
answer
53
views
About the congruence $ax^{8}+bx^{4}+c\equiv 0 \pmod {2^{x}}$
I have a congruence of the form:
$$ax^{8}+bx^{4}+c\equiv 0 \pmod {2^{x}}$$
where $a,b,c$ are fixed integers and $x>0$ is the unknown integer.
I want to see if there is some sufficient an necessary ...
- 61.4k
5
votes
7
answers
314
views
Why does the equation $x^2\equiv2 \pmod 5$ have no solutions?
Why does the equation $x^2\equiv2 \pmod 5$ have no solutions?
I did a remainders table and found that $$x^2\equiv0;1;4\pmod 5$$
But is there any way to justify this besides that?
The original ...
- 64.3k
1
vote
0
answers
63
views
Complete Residue System Modulo $z$ in the Gaussian Integers
Let $z \neq 0$ be a non-unit Gaussian integer. I wish to prove that the Gaussian integers in the fundamental parallelogram associated to $z$ are a complete residue system modulo $z$. I have succeeded ...
- 183
0
votes
1
answer
73
views
$\exists X, Y, Z \in \mathbb{Z}[\omega]$ such that $X^3 + Y^3 + Z^3 = \omega$?
I am considering the following problem: Denote by $\mathbb{Z}[\omega]$ the set of Eisenstein integers. Let $X, Y, Z \in \mathbb{Z}[\omega]$ be non-zero integers coprime to $1-\omega$. Is it possible ...
- 128k
0
votes
2
answers
126
views
Inconsistent definitions of "quadratic residue" versus (linear) "residue"?
The Legendre symbol $(94 / 59)$ is equal to $1,$ so, by definition, $94$ is a quadratic residue mod $59.$
Meanwhile, the residue of $a\mod n$ is defined as the (positive) remainder when $a$ is divided ...
- 38k
11
votes
4
answers
719
views
Does the Diophantine equation $z_1^5 +z_2^5+z_3^5+z_4^5+z_5^5=\beta^5$ have a solution for every integer $\beta$?
(Note: The exponent $k=3$ has been answered in the affirmative in this post.)
I. Data
For simplicity, assume all terms $\in \mathbb{Z},$ so we can transform the equation to the more symmetric,
$$x_1^...
- 52.3k
4
votes
1
answer
76
views
$G = \{c \in \{1, 2, \ldots, n-1\} \mid \gcd(c,n) = 1\},H = \{c \in G \mid \text{ord}(c) \text{ is odd}\}$ Proof H is closed under multiplication
Defining the Groups:
$G = \{c \in \{1, 2, \ldots, n-1\} \mid \gcd(c,n) = 1\}$ represents the group of units mod $n$. These are the integers in the range $1$ to $n-1$ that are coprime to $n$.
$H = \{c ...
- 351
1
vote
1
answer
44
views
$ \left\lfloor\frac{x - \pi(z)^*}{n} \right\rfloor\geq\left\lfloor\frac{x-z^*}{m}\right\rfloor $ whenever $n\mid m$ and $\pi:\Bbb{Z}/m\to\Bbb{Z}/n$✨
If $z \in \Bbb{Z}/n$, w let $z^* =$ the standard residue or in other words the least non-negative integer equal to $z$ modulo $n$. Suppose that $n \mid m$ for some two positive integers $n,m$.
If $\pi ...
- 20.8k
1
vote
3
answers
1k
views
Multiplicative group of integers modulo $p$
$\mathbb{Z}/7\mathbb{Z}=\{1,2,3,4,5,6\}$.
$6\times 6=1~{\rm mod}~ 7$ implies $6$ is an element of order $2$; however, we know that $\mathbb{Z}/7\mathbb{Z}\cong C_7$, not containing an element of ...
- 770
4
votes
4
answers
676
views
General divisibility tests of form $\, 7\mid10b+a\!\iff\! 7\mid b-2a\!\iff\! 7\mid b+5a$.
I am currently helping a friend with their problem sheet. They have been given the question
Let $n\in\mathbb{N}$ have digits $a_r, \dots a_1,a_0$, so that
$$n=10^ra_r+\dots+10^2a_2+10a_1+a_0 = 10b+...
- 267k
2
votes
2
answers
2k
views
Using gcd Bezout identity to solve linear Diophantine equations and congruences, and compute modular inverses and fractions
Isn't finding the inverse of $a$, that is, $a'$ in $aa'\equiv1\pmod{m}$ equivalent to solving the diophantine equation $aa'-mb=1$, where the unknowns are $a'$ and $b$? I have seem some answers on this ...
- 267k
0
votes
0
answers
21
views
Congruence and cases proof [duplicate]
My question is specifically regarding congruence and the use of cases with the definition. I am only using the below mentioned example to emphasis my question.
I have a definition of congruence in my ...
- 267k
25
votes
2
answers
11k
views
$\bmod n\!:\ a^n \equiv 1\!\iff\! $ order of $a$ divides $n,\,$ e.g. when $\,n = \phi(m)$
How can I show that the order of an element modulo $m$ divides $\phi(m)$?
I know that if $a$ and $m$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod m$ is its ...
- 267k
1
vote
1
answer
44
views
Pollard’s rho method: use the polynomial $f(x) = x^2$, show for $j<i$, $a_i ≡a_j \pmod p ⇔ 2^{i−1} ≡2^{j−1} \pmod k$, $p$ is a prime factor of $n$ [duplicate]
Let $n > 1$ be a number which we wish to factorize. Suppose we
try to change the implementation of Pollard’s rho method to use the polynomial $f(x) = x^2$ instead. That is,
we define our sequence $...
- 267k
0
votes
1
answer
62
views
Modulus with negative number
Modular arithmetic with positive Integer can be describe with clock system where we usually wrap an number with an number like 13 that warp the number of 1. But how if in modular arithmetic use an ...
- 21.2k
5
votes
3
answers
1k
views
Negative modulus
In the programming world, modulo operations involving negative numbers give different results in different programming languages and this seems to be the only thing that Wikipedia mentions in any of ...
- 59.4k
5
votes
5
answers
1k
views
Why 9 mod -7 = -5? Quotient and remainder with negative integers.
Forgive me if this question does not belong on this site for it is simplistic and this is my first post, however I do not seem to understand the modulo function when it comes to negative numbers.
I'd ...
- 267k
0
votes
1
answer
65
views
n = pq where p and q are odd prime numbers, gcd(c,n) = 1, c < n, show at most $\frac{φ(n)}{4}$ of c satisfy $ord_n(c)$ is odd
Suppose n = pq where p and q are distinct odd prime numbers. Show that, out of the φ(n) different integers c satisfying 1 < c < n and gcd(c,n) = 1, at most $\frac{φ(n)}{4}$ of them have
the ...
- 131
4
votes
2
answers
1k
views
Do the parentheses around modulo matter
According to wiki's Modular Arithmetic page:
...denoted ${\displaystyle a\equiv b{\pmod {n}}.}$
(some authors use $=$ instead of $≡$ ; in this case, if the parentheses are omitted, this generally ...
- 59.4k
29
votes
6
answers
51k
views
mod [= remainder] operation (and relation), name and meaning
I am trying to write the Euclidean algorithm in the following way:
$A = \lfloor A \div B \rfloor \times B + (\text{remainder of}) \: A \div B $
Now is there any symbol I can use to say "remainder ...
- 267k
0
votes
0
answers
29
views
Form Of Modular Arithmetic [duplicate]
In modular arithmetic there is 2 form :
$a\pmod n$
$a\bmod n$
But,What is the different between this 2 form
- 267k
6
votes
2
answers
452
views
Chinese reminder Theorem and primitive roots
The problem I am working on is "Let $p$ be a prime such that $p\equiv 1\pmod{105}$. Show that there exist integers $n, x, y, z$ such that $p$ does not divide $n$ and $n \equiv 3x^3 \equiv 5y^5 \equiv ...
- 511
2
votes
2
answers
81
views
Proving that $(x-2)^3 = 3 \text{ mod 13}$ admits no solutions [duplicate]
I wish to prove that $(x-2)^3 = 3 \text{ mod 13}$ admits no solutions. Admittedly, I could always plug in the numbers $0, 1, 2, ..., 12$ and show that for each of them $(x-2)^3$ is not congruent to $...
- 9,225
0
votes
0
answers
86
views
Find all natural numbers $n$ less than 100...
Find all natural numbers $n$ less than $100$ such that $n^{122} - 96n^{81}$ ends in the digits $77$.
To do this problem, I first tried using Fermat's little theorem, where $n^{7-1} ≡ 1\ (mod\ 7)$, but ...
- 267k
0
votes
2
answers
177
views
Where is the mistake in this reasoning?
If we make a table such that each column contains numbers modulo $m$ and each row containing numbers modulo $n$. Let us denote the element $a_{ij}=x$ and $a_{i'j'}=y$ Where $0\leq i,i'<...
- 267k
2
votes
2
answers
301
views
Show that if $n$ divides $a^n-b^n$ then $n$ divides $\frac{a^n-b^n}{a-b}$
Let $a,b,n \in \mathbb Z^+$. Show that if $n$ divides $a^n-b^n$ then $n$ divides $\frac{a^n-b^n}{a-b}$.
This is from Apostol’s Introduction to Analytic Number Theory, Chapter $5$, exercise $13$.
It ...
0
votes
1
answer
89
views
Why am I wrong: counting polynomials with degree at most $d$ in $\pmod p$ using value representation
When working with polynomials in mod $p$ (restricting the coefficients and $x$-values to numbers in $\{0,\ldots, m-1\}$ where $p$ is prime), I am getting that the number of polynomials of at most ...
- 32.7k
1
vote
1
answer
33
views
Extending the usefulness of xor for identifying items not in a sequence.
Given the sequence [0 .. 255]
If a single value is removed, the xor of the remaining values produces that missing value.
However, if two values are removed, This no longer works.
A. Why does this ...
- 45.3k
0
votes
1
answer
25
views
Congruences involving central binomial coefficients
When $p$ is prime, one easily checks that ${2p \choose p} \equiv 2 \mod p$. Moreover, if $p \le 31$, we have even ${2p \choose p} \equiv 2 \mod p^2$. Is this true for all prime numbers? Is it easy to ...
- 67k
-3
votes
1
answer
90
views
Show that the equation $5x = 3$ modulo 20 has no integer solution [duplicate]
This question is half of a larger question:
Show that the equation $5x = 3$ modulo $20$ has no integer solution but $3x = 5$ does.
I can show that $3x = 5$ has an integer solution in $U(20)$ by using ...
- 267k
25
votes
6
answers
734
views
Fibonacci-esque sequences modulo $1$: what is the largest possible infimum?
Let an infinite sequence $S$ be a "Fibonacci-esque sequence" if, for all $n \geq 3, S(n) = S(n-1) + S(n-2).$ We can reduce $S$ modulo $1$ to get a "reduced Fibonacci sequence." ...
- 3,831