Questions tagged [congruences]
The congruences tag has no usage guidance.
110
questions
5
votes
0
answers
315
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 ...
- 13k
2
votes
1
answer
109
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 ...
- 17.3k
4
votes
2
answers
204
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<...
- 23.7k
5
votes
0
answers
150
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,...
- 111
4
votes
2
answers
181
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}$ ?
...
- 613
6
votes
1
answer
499
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 \...
- 269
3
votes
2
answers
890
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)\...
- 629
7
votes
2
answers
706
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 ...
- 567
1
vote
0
answers
135
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 ...
- 13k
3
votes
1
answer
159
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$ ...
- 13k
5
votes
2
answers
257
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}+...
- 13k
3
votes
1
answer
133
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$...
- 894
0
votes
0
answers
74
views
On $q$, $k$ modulo $3$ and the residue of $\sigma(n^2)$ modulo $x$ when $q^k n^2$ is an odd perfect number with special prime $q$
Chen and Luo (now published) proved in Theorem 3.3, page 7 that if $m = q^k n^2$ is an odd perfect number with special prime $q$, then we have the biconditionals
$$\sigma(n^2) \equiv 1 \pmod 4 \iff q \...
- 1,394
10
votes
1
answer
556
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 ...
- 13.3k
1
vote
1
answer
82
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$ ...
- 539
2
votes
0
answers
53
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^{...
- 21
8
votes
1
answer
247
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 ...
- 13k
7
votes
2
answers
345
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} \\
...
- 383
1
vote
1
answer
152
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,\\
...
- 13
11
votes
1
answer
534
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:...
- 13k
8
votes
1
answer
259
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
146
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,643
1
vote
0
answers
108
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 ...
- 137
1
vote
0
answers
139
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}\ ...
- 13k
18
votes
0
answers
709
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)$ ...
- 13k
7
votes
0
answers
172
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....
- 13k
6
votes
0
answers
188
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,\...
- 13k
2
votes
0
answers
114
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 ...
- 19
0
votes
0
answers
172
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 ...
user147204
0
votes
0
answers
81
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^...
- 2,123
0
votes
1
answer
168
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$ ...
- 103
4
votes
0
answers
131
views
Is it true that $|\{k^{k+1}+(k+1)^k\pmod p:\ k=0,\ldots,p-1\}|=(1-e^{-1})p+O(\sqrt{p})\ ?$
For each prime $p$, let us define
$$w_p:=|\{k^{k+1}+(k+1)^k\pmod p:\ k=0,\ldots,p-1\}|,$$
where $a\pmod p$ denotes the residue class $a+p\mathbb Z$.
Based on my computation, I conjecture that
$$w_p=...
- 13k
6
votes
1
answer
229
views
Corollaries of the halo conjecture that do not involve the eigencurve
In the theory of p-adic modular forms there is a certain construction called the Coleman-Mazur eigencurve. The spectral halo conjecture roughly states that if you remove a closed subdisc of the weight ...
user145520
3
votes
0
answers
156
views
Congruences of modular forms modulo other modular forms
Congruences between modular forms are certainly a big topic in number theory, maybe with
$$E_{p-1}\equiv 1 \mod p \qquad \text{for a prime }p\geq 5$$
as the easiest example. Sometimes, $p$ might be ...
- 11.4k
6
votes
0
answers
208
views
Two conjectural congruences for Franel numbers
Recall that the Franel numbers are given by
$$f_n:=\sum_{k=0}^n \binom{n}{k}^3\ \ \ (n=0,1,\ldots).$$
Question. How to prove my following conjecture?
Conjecture. For each odd prime $p$, we have
$$\...
- 13k
7
votes
0
answers
194
views
Does Morley's congruence characterize primes greater than $3$?
In 1895 Morley showed that $$\binom{p-1}{(p-1)/2}\equiv(-1)^{\frac{p-1}2}4^{p-1}\pmod{p^3}$$
for any prime $p>3$.
In 2009, I formulated the following conjecture concerning the converse of Morley's ...
- 13k
2
votes
0
answers
53
views
Is it possible to deduce statements for odd perfect numbers from the convolution sums involving divisor functions or other arithmetic functions?
Dividing and using some identities of [1] I've deduced the following facts, see also the remarks below. After these introductory paragraphs, to motivate our question, I am asking if we can deduce some ...
- 73
1
vote
1
answer
153
views
Chinese Remainder Theorem for Remainder Intervals
Given $n$ natural numbers $m_1,\dots,m_n$ and $n$ remainder intervals $[a_1,b_1],\dots,[a_n,b_n]$ holding $a_i < b_i$ for all $i\leq n$ the task is to search for the smallest natural number $x$ ...
- 11
3
votes
0
answers
206
views
An attempt to get a variant of Agoh–Giuga conjecture
The idea of this post is an attempt to explore a variant of the so-called Agoh–Giuga conjecture. In past days, and today, I tried to think about variants of this conjecture exploring congruences about ...
- 73
7
votes
0
answers
199
views
How to prove the identity $\sum_{k=1}^\infty\frac{3H_{k-1}^2+4H_{k-1}/k}{k^2\binom{2k}k}=\frac{\pi^4}{360}$?
For each $n=0,1,2,\ldots$, the harmonic number $H_n$ is given by
$$H_n:=\sum_{0<k\le n}\frac1k.$$
In 2016 I conjectured that
$$\sum_{k=1}^\infty\frac{3H_{k-1}^2+4H_{k-1}/k}{k^2\binom{2k}k}=\frac{...
- 13k
2
votes
0
answers
94
views
$\varphi(m+n)\mid n$ for some positive integer $n$
Let $\varphi$ be Euler's totient function.
If $p$ is a prime, then $\varphi(1+n)=n$ for $n=p-1$.
Question. Is it true that for each integer $m>1$ there is a positive integer $n\le m^2-m$ such that ...
- 13k
1
vote
1
answer
197
views
A divisibility problem involving Catalan numbers
The Catalan numbers in combinatorics are given by
$$C_n=\frac1{n+1}\binom{2n}n=\binom{2n}n-\binom{2n}{n+1}\ \ (n=0,1,2,\ldots).$$
In 2014 I formulated the following conjecture.
Conjecture. For each $...
- 13k
5
votes
0
answers
269
views
Is an algebraic number satisfying certain super-congruences a root of unity?
Let $K|\mathbb{Q}$ be a number field, $D$ its discriminant and $\mathcal{O}$ the ring of integers in $K$. Let $x\in K$ (or maybe $\in \mathcal{O}[\frac 1D]$) such that for all primes $p$ in $\mathbb{Q}...
- 161
1
vote
0
answers
44
views
Efficient scissors congruence between efficiently describable convex polytopes and simplex?
Is there a convex polytope in $\mathbb R^n$ describable by only $O(poly(\log n))$ half-plane inequalities with positive volume (so at least $n+1$ vertices) such that the standard simplex has a ...
- 1,728
5
votes
1
answer
299
views
Reversing the CRT: Is $5$ tough?
Given odd primes $p\ne q$, by the CRT we can find an integer $x$ such that $x\equiv 2^{p-1}\pmod q$ and $x\equiv 2^{q-1}\pmod p$. Can this procedure be reversed?
For which integers $x$ there exist ...
- 550
1
vote
0
answers
62
views
Wieferich primes and arithmetic prgressions
Let $p$ be an odd prime number. Let $K$ be a number field with Galois group $G$ and $H$ be a subgroup of $G$ stable under conjugation. Then the Cebotarev density theorem gives that $$\mathcal{L}=\{\...
- 299
1
vote
1
answer
97
views
Density of a set of numbers dividing a fixed number with polynomial exponent
Fix a positive integer $a>1$ and let $f\in\mathbb{Z}[x]$ be a polynomial with positive leading coefficient. We define a set $S$ of positive integers,
$$
S=\{n\in\mathbb{Z}^+:n\mid a^{f(n)}-1\}.
$$
...
- 1,076
2
votes
1
answer
178
views
Number of odd elements in a vanishing sum of binomial coefficients
Let $n$ be a positive integer, $k$ a non-negative integer and $N(n,k)$ be the number of odd elements among the numbers $\binom{n+k}{j}\binom{-n-k}{n-j}$, $0\le{j}\le{n}$, which sum to $0.$ It seems ...
- 5,103
12
votes
4
answers
2k
views
Prove that $\sum_{n = 1}^{p - 1} n^{p - 1} \equiv (p - 1)! + p \pmod {p^2}$ with $p$ being an odd prime
First, I have to admit that I have already asked the same question on MSE several days ago. If I am bending any rules, I apologize for that and moderator can delete or close this question without ...
- 223
9
votes
1
answer
332
views
On the permanent $\text{per}[i^{j-1}]_{1\le i,j\le p-1}$ modulo $p^2$
Let $p$ be an odd prime. It is well-known that
$$\det[i^{j-1}]_{1\le i,j\le p-1}=\prod_{1\le i<j\le p-1}(j-i)\not\equiv0\pmod p.$$
I'm curious about the behavior of the permanent $\text{per}[i^{j-...
- 13k