Questions tagged [congruences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
  • 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<...
user avatar
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,...
user avatar
  • 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}$ ? ...
user avatar
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 \...
user avatar
  • 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)\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
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}+...
user avatar
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$...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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^{...
user avatar
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 ...
user avatar
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} \\ ...
user avatar
  • 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,\\ ...
user avatar
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:...
user avatar
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 ...
user avatar
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^...
user avatar
  • 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 ...
user avatar
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}\ ...
user avatar
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)$ ...
user avatar
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....
user avatar
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,\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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^...
user avatar
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$ ...
user avatar
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=...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $$\...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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{...
user avatar
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 ...
user avatar
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 $...
user avatar
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}...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}=\{\...
user avatar
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\}. $$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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-...
user avatar