# 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
Filter by
Sorted by
Tagged with
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 ...
1 vote
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$$ ...
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 ...
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.
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 ...
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 ...
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 ...
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$. ...
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$ ...
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
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 ...
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 ...
28 views

29 views

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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
719 views

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 ...
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 ...
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 ...
1 vote
44 views

81 views

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 ...
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 ...
1 vote
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 ...
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 ...
### 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 ...
### 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." ...