# Questions tagged [congruences]

The congruences tag has no usage guidance.

133
questions

1
vote

1
answer

49
views

### Complexity of solving system of binary quadratic equations modulo $3$

A special case of this question and
another question
What is the complexity of solving system of binary quadratic equations modulo
$3$?
$f_i(x_i,x_j)=0 \bmod 3, \deg{f_i}=2$.
Modulo $2$ can be ...

-2
votes

0
answers

145
views

### On the congruential equidistribution of $3^n \bmod 2^n$

I am interested in the asymptotic congruential equidistribution of $u_n = 3^n \bmod 2^n$ in the set of positive odd integers, as $n\rightarrow \infty$. Or the asymptotic congruential equidistribution ...

2
votes

1
answer

362
views

### Prove ${^{b}a} \equiv {^{b+1}} a \pmod {10^{\lfloor{\log_{10} (^{b}a) }\rfloor + 1}} \Rightarrow a=5$ as $a$ and $b$ are two integers greater than $1$

$\DeclareMathOperator\len{len}$Let $a, b \in \mathbb{N} -\{ 0, 1 \}$ and define ${^{b}a}$ to be $a^a$ if $b = 2$ and $a^{\left(^{b-1}a \right)}$ if $b \geq 3$ (e.g., ${^{3}5} = 5^{\left( 5^5 \right)} =...

4
votes

0
answers

169
views

### Congruences between hypergeometric functions coming from modular forms

Consider the formal power series
$${}_2F_1(1/12,5/12;1;z)^{24}-{}_2F_1(1/12,7/12;1;z)^{24}=-z/3-z^2/2-(320293/559872)z^3-\cdots$$
It follows from a theorem on modular forms that for $p\ge5$ the ...

0
votes

0
answers

50
views

### Factorial quadratic residue

I would like to find all positive integers $n$ and $m$ such that $n^2 \equiv m! \ ( \text{mod } 2024)$. I see that for $m=1$ there is $n=45$ such that the relation holds.
I think that there is no ...

1
vote

1
answer

95
views

### Number of solutions for linear modular equations given GCD

We are currently investigating a problem involving number theory, an area outside our field of expertise.
Let $n$ be a positive integer. Consider two pairs of integers $(j,k)$ and $(j′,k′)$ as ...

4
votes

1
answer

234
views

### About the exact origin of a binomial congruence

Given a prime $p$ and an integer $0 \leq k \leq p-1$, a famous congruence on binomial coefficients states:
$$\binom{p-1}{k} \equiv (-1)^k \pmod{p}$$
It is generally taught as a consequence of Pascal’s ...

0
votes

0
answers

124
views

### Defining the number of rightmost frozen digits of Graham's number

It is well-known that (in radix-$10$) Graham's number, $G$, can be expressed as a tetration with base $3$ and a very large hyperexponent $\tilde{b}$. Thus, we can write that $\exists! \hspace{1mm} \...

1
vote

1
answer

242
views

### A vanishing sum and related $p$-adic congruences

Recently I had a curious discovery. Namely, I have made the following conjectures.
Conjecture 1. We have the identity
$$\sum_{k=0}^\infty\frac{(10k-1)\binom{3k}k\binom{6k}{3k}}{(2k+1)512^k}=0.\label{1}...

2
votes

1
answer

401
views

### Chinese remainder theorem for target interval

Given $n$ pairwise coprime natural numbers $m_{1}, \dots, m_{n}$ with remainders $y_{i}$, for all $i \leq n$. Furthermore, we have a target interval $I := \left[ a, b \right]$, with $1 \leq a < b \...

8
votes

0
answers

327
views

### A hypergeometric series for $\sqrt3\pi$ with converging rate $1/9$

Recently, I found a (conjectural) new series for $\sqrt3\pi$:
$$\sum_{k=1}^\infty\frac{(8k-3)\binom{4k}{2k}}{k(4k-1)9^k\binom{2k}k^2}=\frac{\sqrt3\pi}{18}.\label{1}\tag{1}$$
The series converges fast ...

6
votes

2
answers

642
views

### Number of solutions of $am \equiv bn \pmod{q}$

Let $q$ be a (large) prime. Let $N$ be a positive integer of size${}\approx \sqrt{q}$. Let $\mathcal{M}$ be an arbitrary subset of $\{1, \dots, q\},$ such that $\mathcal{M}$ has cardinality $N$. ...

3
votes

1
answer

386
views

### A combinatorial identity involving binomial coefficients

When I was reading an article by CHUN-GANG JI (A SIMPLE PROOF OF A CURIOUS CONGRUENCE BY ZHAO), he mentioned in the acknowledgement
the following identity
$$\sum_{i+j+k=p,\text{ } i,j,k\gt 0}{p\choose ...

3
votes

0
answers

322
views

### When are modular forms linearly independent modulo $p$?

Let $M_2(\Gamma_0(N))$ be the space of weight $2$ modular forms for $\Gamma_0(N)$ and let $f_1, \dots, f_r$ be a basis of normalized eigenforms for $M_2(\Gamma_0(N))$. Given a rational prime $p$, I'll ...

5
votes

2
answers

271
views

### Modulo $x^2 + y^2 - 1$, is every homogeneous polynomial that is a square of a polynomial, necessarily of sum of squares of homogeneous polynomials?

I am hoping this question is alright for Math Overflow. I didn't get a definitive solution in Math Stack Exchange.
Let $f(x, y) \in \mathbb{R}[x, y]$ be a homogeneous polynomial with real coefficients ...

13
votes

1
answer

575
views

### A congruence for a product of binomial coefficients?

For every prime $p\geq 5$ one seems to have the congruence
$$(-1)^{(p-1)/2}\prod_{k=0}^{p-1}{p-1\choose k}\equiv 1-p+\frac{3}{2}p^2-\frac{7}{6}p^3\pmod{p^4}\ .$$
(I have checked all primes up to $5000$...

5
votes

2
answers

427
views

### "Efficient" way to build a table of multiplicative orders modulo $p$ of a fixed integer $a$

Given an integer $a$, I would like to build a table of entries $(p, \text{ord}_p(a))$, where $p$ runs over the prime numbers not dividing $a$ and not exceeding a fixed parameter $P$, and $\text{ord}_p(...

3
votes

2
answers

615
views

### Binomial coefficient congruence modulo $p^n$

I am interested in the following congruence
$$\binom{ap^n}{bp^n}\equiv \binom{a}{b}\pmod{p^n}$$
I am aware that by some reference in a book the above it should actually hold modulo $p^{3n}$; the ...

8
votes

2
answers

249
views

### Congruences of binomial sums

Let $a_n$ is a binomial sum, for example
$$
a_n := \sum_{k} \binom{n-k}{k} \quad \text{or} \quad \sum_{k=0}^n\binom{n+k}{n-k}\binom{2k}{k}
\quad \text{or} \quad \sum_{k=0}^n\sum_{\ell=0}^k\binom{n}{k}\...

2
votes

1
answer

132
views

### Primitive representation of integers by some form on the genus of a quadratic form

Some time ago, I asked a question about equidistribution on a paper of Duke and Schulze-Pillot that was usefully answered.
However, on the answer there was a statement that was unimportant for me back ...

3
votes

1
answer

74
views

### Reference request for a proof of the Mal'cev condition for congruence $n$-permutability

By a theorem of Hagemann and Mitschke, a condition (A) that a variety $\mathcal{V}$ is congruence $n$-permutable, is equivalent to a condition (B) that there exist ternary terms $p_1,\dots,p_{n-1}$ ...

0
votes

2
answers

130
views

### Binomial congruence modulo prime [closed]

Let $a$, $b$ $(b≤a)$ be two positive integers are not twin primes and $p$ is any prime number.
Is this congruence
$$ \binom{a^p}{b^p} \equiv \binom{a}{b}^p \pmod{p} $$
valid?

0
votes

0
answers

132
views

### Which consequences can be deduced from this peculiar property of tetration?

Recently (assuming radix-$10$), I showed that, for any $a \in \mathbb{N}_{0}$ that is not a multiple of $10$, there exists a unique value $V(a) \in \mathbb{N}_{0}$ which corresponds to the number of ...

1
vote

0
answers

173
views

### Some $p$-adic congruences involving permutations

Motivated by my study of determinants and permanents, here I present several conjectures on $p$-adic congruences involving permutations.
As usual, we let $S_n$ be the symmetric group consisting of all ...

5
votes

0
answers

522
views

### Two conjectures for primes $p\equiv 1\pmod 8$

Motivated by my paper Quadratic residues and quartic residues modulo primes [Int. J. Number Theory 16 (2020), 1833-1858], here I pose two new conjectures for primes $p\equiv1\pmod8$ based on my ...

2
votes

1
answer

131
views

### Conjectural congruences for numbers related to Littlewood-Richardson coefficients

For $n \geq 0$, let $a_n$ be the square of the Euclidean length of the vector of Littlewood-Richardson coefficients of $\sum_{\lambda \vdash n} s_\lambda^2$, where $s_\lambda$ are the symmetric Schur ...

4
votes

2
answers

212
views

### Least modulus distinguishing some integers

I can deduce some results about this from the prime number theorem or from results about the primorial function $p\#$ but I'm wondering what the state of the art is:
Given integers $0\le a_1<a_2<...

5
votes

0
answers

203
views

### Number of solutions of linear congruence with bounded variables

Fix some nonzero integers $a_1, \dots, a_k$, with $k \geq 2$, and some real numbers $c_1, \dots, c_k \in (0,1)$.
For every positive integer $m$, let $N(m)$ be the number of $k$-tuple of integers $(x_1,...

4
votes

2
answers

200
views

### System of congruences with bound condition

Let $m$ be a positive integer divisible by $6$, and let $q$ be one of $8,9$,
or a prime $\gt 3$.
Question : Is there always an $x\in [1,m]$, coprime to $m$, such
that $x\not\equiv\pm 1 \ \mod{q}$ ?
...

6
votes

1
answer

566
views

### Are there finitely many primes $x$ such that for a fixed odd prime $p$, $n=x^{p-1}+x^{p-2}+\dotsb + x+1$ is composite and $x \mid \phi(n)$?

Let
\begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1
\end{equation} where $x$ and $p$ are odd primes.
If $p$ is set to $5$, it appears $x=5$ is the only prime $x$ such that $n$ is composite and $x \...

4
votes

2
answers

917
views

### A conjecture about 433

Motivated by Question 405105, I found the following
Conjecture. $2^{2n}-2^n+1 \equiv 0 \pmod {433}$ and $n=4m$ iff
$$\phi(m) = \phi(i + j) = \phi(i) + \phi(j) ,$$
and
$$\phi(m) = \phi(ik) = \phi(i)\...

7
votes

2
answers

770
views

### Could a nice principle be extracted from this lemma of Gauss

I asked the following question in the math SE, with a bounty of 200 pts, without result.
question:
To prove the quadratic reciprocity law, Gauss needed the following lemma:
If $p$ is a prime number ...

1
vote

0
answers

138
views

### The congruence $\mathrm{per}[|j-k|]_{1\le j,k\le p}\equiv-1/2\pmod p$ with $p$ an odd prime

For a matrix $[a_{j,k}]_{1\le j,k\le n}$, its permanent is given by
$$\mathrm{per}[a_{j,k}]_{1\le j,k\le n}=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$
Let $p$ be an odd prime. I have proved the ...

3
votes

1
answer

172
views

### Does $\{\tau(1)\tau(2)+\cdots+\tau(n-1)\tau(n)+\tau(n)\tau(1):\ \tau\in S_n\}$ contain a unique multiple of $n^2$ for each $n\ge6$?

Motivated by Question 397575, here I pose a related question.
Question.
Does the set $$T_n:=\{\tau(1)\tau(2)+\cdots+\tau(n-1)\tau(n)+\tau(n)\tau(1):\ \tau\in S_n\}$$ contain a unique multiple of $n^2$ ...

5
votes

2
answers

334
views

### Permutations $\pi\in S_{p-1}$ with $\frac1{\pi(1)\pi(2)}+\frac1{\pi(2)\pi(3)}+\cdots+\frac1{\pi(p-2)\pi(p-1)}+\frac1{\pi(p-1)\pi(1)}\equiv0\pmod{p^2}$

A well known congruence of Wolstenholme states that
$$\frac1{1^2}+\frac1{2^2}+\cdots+\frac1{(p-1)^2}\equiv0\pmod{p}$$ for any prime $p>3$. For each $n=3,4,\ldots$ we clearly have
$$\frac1{1\times2}+...

3
votes

1
answer

295
views

### The invertible matrices $S$ that satisfy $A=SDS^T$

Any real symmetric matrix $A$ can be written as $A=SDS^T$ for some diagonal matrix $D$ and invertible matrix $S$. Let's fix $D$ to be the (diagonal) inertia matrix of $A$, which has an entry $1, -1, 0$...

11
votes

1
answer

634
views

### A conjecture on binomial coefficients and roots of unity

Is the following true?
Let $p$ be a prime and let $w$ be a $(p-1)$st root of unity (not necessarily primitive). Then
$$\binom{w}{n}=\frac{w(w-1)\cdots(w-n+1)}{n!}$$ is $p$-integral; i.e., it can be ...

1
vote

1
answer

89
views

### Can a polynomial be evaluated from evaluations of partial interpolations? (Or: can the unique solution of congruences be written in a certain way?)

Formally, let $K$ be a field, $a \in K[x]$, $D \subseteq K$, and $E = \{(x_i, a(x_i)) \mid x_i \in D\}$ be distinct evaluations of $a$ where $\lvert E\rvert > \operatorname{deg}(a)$ (so $E$ ...

2
votes

0
answers

62
views

### Solution distribution in a quadratic congruence

Fix a modulus $M$. For varying $m$, consider the (possibly empty) set $R_{m,M}$ of roots of $x^2\equiv m^2+2 \pmod{M}$.
Are there good known bounds on
$$\sum_{m\le M^{1/100}}\sum_{r\in R_{m,M}}\min(M^{...

8
votes

1
answer

281
views

### On the determinant $\det[\gcd(i-j,n)]_{1\le i,j\le n}$

In Sept. 2013, I investigated the determinant
$$D_n=\det[\gcd(i-j,n)]_{1\le i,j\le n}$$
and computed the values $D_1,\ldots,D_{100}$ (cf. http://oeis.org/A228884). To my surprise, they are all ...

7
votes

2
answers

372
views

### Is there a nonzero solution to this infinite system of congruences?

Is there a triple of nonzero even integers $(a,b,c)$ that satisfies the following infinite system of congruences?
$$
a+b+c\equiv 0 \pmod{4} \\
a+3b+3c\equiv 0 \pmod{8} \\
3a+5b+9c\equiv 0 \pmod{16} \\
...

1
vote

1
answer

159
views

### A special congruence

For any $a, b\in\mathbb{N}$ with $a+2b\not\equiv 0\pmod 3$, we define $\delta(a, b)$ as follows:
\begin{align*}
\delta(a, b)={\left\{\begin{array}{rl}
1,\ \ \ \ &{\rm if} \ a+2b\equiv 1\pmod 3,\\
...

12
votes

1
answer

829
views

### Numbers $k$ with $\{\binom nk:\ n\in\mathbb N\}$ dense in $\mathbb Z_p$ for any prime $p\le k$

Let $k$ be a positive integer and let $p$ be a prime. In my 2011 PAMS paper joint with my former student W. Zhang [Proc. Amer. Math. Soc. 139(2011), 1569-1577], we studied when $$S(k)=\left\{\binom nk:...

8
votes

1
answer

317
views

### Subgroups of Sp(2g,Z) that map onto all Sp(2g,Z/m)

I stumbled into the following problem. I apologize for being a bit naive.
For $g\geq 3$, consider the group $\mathrm{Sp}(2g,\mathbb{Z})$ of symplectic square matrices of order $2g$ with integral ...

3
votes

1
answer

190
views

### Solutions to nonhomogeneous quadratic equation mod $N$

Is there any way to find non-trivial solutions to the equation $x^2 + y^2 - x \equiv 0 \mod{N}$? There are clearly several trivial solutions, for example $(x, y) = (0, 0), (1, 0), (2^{-1}, 2^{-1}), (2^...

1
vote

0
answers

173
views

### Probability of satisfying the congruent mod equation

I'm wondering about the probability of picking three different numbers $x,y,z$ out of the set $[50]=\left\{ 1,2,3,...,50\right\}$ satisfying the equation: $$xyz\equiv \gcd(x,y,z)\mod 7$$ I started out ...

1
vote

0
answers

152
views

### An explicit solution to the congruence $x^2\equiv 14(\frac 3p)-(\frac p3)-12\pmod {p}$?

Let $p>3$ be a prime, and let $(\frac{\cdot}p)$ be the Legendre symbol. Then
$$14\left(\frac 3p\right)-\left(\frac p3\right)-12=\begin{cases}1&\text{if}\ p\equiv1\pmod{12},
\\-25&\text{if}\ ...

18
votes

0
answers

750
views

### Two curious series for $1/\pi$

On Jan. 18, 2012 I conjectured that for any prime $p>3$ we have
$$R_p^2\equiv\frac1{10}\left(512\left(\frac{10}p\right)-27\left(\frac{-15}p\right)-475\right)\pmod p,$$
where $(\frac{\cdot}p)$ ...

7
votes

0
answers

182
views

### Some conjectural congruences involving Domb numbers

The Domb numbers are given by
$$D_n=\sum_{k=0}^n\binom{n}{k}^2\binom{2k}k\binom{2(n-k)}{n-k}\ \ \ (n=0,1,2,\ldots).$$
Such numbers have combinatorial interpretation, see, e.g., http://oeis.org/A002895....

6
votes

0
answers

192
views

### A conjecture involving $P_n=\prod_{k=1}^np_k$

For each positive integer $n$ let $P_n=\prod_{k=1}^n p_k$, where $p_k$ is the $k$th prime.
Question. Is my following conjecture true?
Conjecture. For any integer $n>1$, there are $k,m\in\{1,\...