Questions tagged [congruences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
83 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 ...
HardProblemHero's user avatar
4 votes
1 answer
224 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 ...
Monk's user avatar
  • 125
0 votes
0 answers
121 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} \...
Marco Ripà's user avatar
  • 1,119
1 vote
1 answer
226 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}...
Zhi-Wei Sun's user avatar
  • 14.4k
2 votes
1 answer
379 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 \...
Samdney's user avatar
  • 23
8 votes
0 answers
316 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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
6 votes
2 answers
637 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$. ...
Kurisuto Asutora's user avatar
0 votes
0 answers
43 views

A question about algebraic indicator functions

Let $f \in \mathbb{Z}[x]$ and $m,k \in \mathbb{Z}$. Consider the indicator function $g_f : \mathbb{Z} \to \{1,0\}$ given by \begin{align*} g_f(n) = \begin{cases} 1 &\text{if there exists $r \in \...
matt stokes's user avatar
3 votes
1 answer
382 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 ...
wkmath's user avatar
  • 33
3 votes
0 answers
315 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 ...
Adithya Chakravarthy's user avatar
5 votes
2 answers
261 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 ...
Colin Tan's user avatar
  • 251
13 votes
1 answer
570 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$...
Roland Bacher's user avatar
4 votes
2 answers
362 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(...
Fran's user avatar
  • 43
3 votes
2 answers
509 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 ...
Vlad Matei's user avatar
7 votes
2 answers
236 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}\...
Igor Pak's user avatar
  • 16.3k
2 votes
1 answer
105 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 ...
MathqA's user avatar
  • 313
3 votes
1 answer
63 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}$ ...
Tom's user avatar
  • 133
0 votes
2 answers
127 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?
Kelvin's user avatar
  • 15
0 votes
0 answers
126 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 ...
Marco Ripà's user avatar
  • 1,119
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
5 votes
0 answers
500 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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
2 votes
1 answer
127 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 ...
James Propp's user avatar
  • 19.4k
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<...
Bjørn Kjos-Hanssen's user avatar
5 votes
0 answers
200 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,...
Erik4's user avatar
  • 121
4 votes
2 answers
197 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}$ ? ...
Ewan Delanoy's user avatar
6 votes
1 answer
562 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 \...
ASP's user avatar
  • 319
4 votes
2 answers
916 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)\...
Deyi Chen's user avatar
  • 844
7 votes
2 answers
758 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 ...
MikeTeX's user avatar
  • 677
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
3 votes
1 answer
169 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$ ...
Zhi-Wei Sun's user avatar
  • 14.4k
5 votes
2 answers
317 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}+...
Zhi-Wei Sun's user avatar
  • 14.4k
3 votes
1 answer
257 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$...
Ben's user avatar
  • 1,010
10 votes
1 answer
615 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 ...
Ira Gessel's user avatar
  • 16.2k
1 vote
1 answer
87 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$ ...
Joe Bebel's user avatar
  • 539
2 votes
0 answers
61 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^{...
quser86341's user avatar
8 votes
1 answer
279 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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
7 votes
2 answers
368 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} \\ ...
M Wright's user avatar
  • 403
1 vote
1 answer
158 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,\\ ...
Xiaoer Qin's user avatar
12 votes
1 answer
817 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:...
Zhi-Wei Sun's user avatar
  • 14.4k
8 votes
1 answer
309 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 ...
Gabriele Mondello's user avatar
3 votes
1 answer
182 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^...
Gautam's user avatar
  • 1,693
1 vote
0 answers
164 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 ...
Marek Kryspin's user avatar
1 vote
0 answers
151 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}\ ...
Zhi-Wei Sun's user avatar
  • 14.4k
18 votes
0 answers
746 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)$ ...
Zhi-Wei Sun's user avatar
  • 14.4k
7 votes
0 answers
179 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....
Zhi-Wei Sun's user avatar
  • 14.4k
6 votes
0 answers
191 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,\...
Zhi-Wei Sun's user avatar
  • 14.4k
2 votes
0 answers
151 views

On the smallest solution of a linear congruence

I have the following question. First, consider the following congruence for primes $p\geq 5$: $24x\equiv -1\;(\mbox{mod}\;p)$. The smallest $x$, that is, $1\leq x\leq p-1$ for which the above ...
Jimoni's user avatar
  • 21
0 votes
0 answers
179 views

When is $\phi(a^n+b^n+c^n)=0\mod n$?

A corollary Zsigmondy's Theorem leads to the following congruence (one can look to $(24)$),$\phi(a^n+b^n)=0\mod n$ whenever $a, b$ are coprime and $n \neq 2$ and $(a,b)\neq(1,1)$. (Here $\phi$ is the ...
user avatar
0 votes
0 answers
90 views

Set of primes $p_{1}\equiv 3 \bmod p_{2}$ such that $\phi(2^{\frac{{p_1}-3}{p_2}}-1)\equiv 0 \bmod p_1$ with $p_1,p_2\equiv 3\bmod 4$?

let $p_1$ and $p_2$ be positive primes such that $p_1,p_2 \equiv 3\bmod 4$ and $\phi$ is the Euler totiont function , I want to find the Set of primes $p_{1}\equiv 3 \bmod p_{2}$ such that $\phi(2^...
zeraoulia rafik's user avatar
0 votes
1 answer
224 views

Solve congruence equation where unknown variable is in both sides of congruent operator

I am trying to solve the following equation: $(a*n + c) \mod (b-n) \equiv 0$ and $n$ must be the lowest value in $[0, b-1]$ for example $a=17$, $c=-59$ and $b=128$, the solution is $n=55$ $n=b-1$ ...
Jose Maria's user avatar