Questions tagged [congruences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
78 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
0answers
46 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
1answer
225 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
2answers
333 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
1answer
144 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,\\ ...
6
votes
1answer
342 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
1answer
195 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
1answer
133 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
0answers
77 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
0answers
129 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
0answers
664 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)$ ...
6
votes
0answers
157 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....
0
votes
0answers
23 views

Eigenvector of $U |y \rangle \equiv |xy (mod N) \rangle$, when $ x \le N$ and $x, N$ coprimes

In the book quantum computing and quantum computation of Nielsen and Chuang, in the chapter relating to order-finding, they say that via a simple calculation, an eigenvector of $U |y \rangle \equiv |...
6
votes
0answers
185 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,\...
1
vote
0answers
88 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 ...
0
votes
0answers
168 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 ...
0
votes
0answers
75 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^...
0
votes
1answer
94 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$ ...
4
votes
0answers
128 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=...
6
votes
1answer
189 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 ...
3
votes
0answers
144 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 ...
6
votes
0answers
200 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 $$\...
7
votes
0answers
180 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 ...
2
votes
0answers
49 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 ...
1
vote
1answer
131 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$ ...
3
votes
0answers
155 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 ...
7
votes
0answers
190 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{...
2
votes
0answers
87 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 ...
1
vote
1answer
154 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 $...
5
votes
0answers
267 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}...
1
vote
0answers
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 ...
5
votes
1answer
288 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 ...
1
vote
0answers
60 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}=\{\...
1
vote
1answer
93 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\}. $$ ...
2
votes
1answer
164 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 ...
12
votes
4answers
1k 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 ...
9
votes
1answer
321 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-...
3
votes
2answers
398 views

On the sum $\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$

Motivated by Question 316142 of mine, I consider the new sum $$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$ for any positive integer $n$, where $S_n$ is the symmetric group of all the ...
4
votes
2answers
376 views

Non-torsion part of the abelianisation of congruence subgroups

I've posted this question on math.stackexchange, but haven't gotten any responses so I'm trying here instead. Let $A = F_q[T]$ be the ring of polynomials in one variable with coefficients in a finite ...
2
votes
1answer
173 views

On the function $f_m(p)=\left|\left\{1\leqslant k<\frac p2:\ \left\{\frac{k^m}p\right\}>\frac12\right\}\right|$

Let $m>1$ be an integer and let $p$ be an odd prime. Can we say something nontrivial about $$f_m(p):=\left|\left\{1\leqslant k<\frac p2:\ \left\{\frac{k^m}p\right\}>\frac12\right\}\right|$$ (...
7
votes
1answer
235 views

On $\prod^{(p-1)/2}_{i,j=1\atop p\nmid 2i+j}(2i+j)$ and $\prod^{(p-1)/2}_{i,j=1\atop p\nmid 2i-j}(2i-j)$ modulo a prime $p>3$

QUESTION: Is my following conjecture true? Conjecture. Let $p>3$ be a prime and let $h(-p)$ be the class number of the imaginary quadratic field $\mathbb Q(\sqrt{-p})$. Then $$\frac{p-1}2!!\prod^{...
4
votes
1answer
190 views

On the solvability of the congruence $p^m\equiv m\pmod{n}$

Let $n,p\geq 1$ be integers, and assume that $p$ is a prime. Question. Does there always exist an integer $m\geq 1$ such that $p^m\equiv m\pmod{n}$?
4
votes
0answers
289 views

Congruence for the product of quadratic residues + the product of quadratic non-residues

My question has been here on MSE for a long time, but it has not received a full answer. I bring it here: Find a prime $p$ such that $p \equiv 1 \bmod 4$ and such that the product in the range $[...
1
vote
0answers
70 views

Equivalent condition for Poincare polynomial

I have found a statement in the introduction of the paper 'Sets of Recurrence and Generalized Polynomials' by Bergelson & Haland, which is Result: Given a polynomial $p \in \mathbb{R}[x]$ such ...
7
votes
1answer
367 views

On $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$

Euler's totient function $\varphi$ is multiplicative, and it plays important roles in number theory. QUESTION: Is it true that for each integer $m>6$ we have $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$...
4
votes
0answers
196 views

Number of power residues modulo prime power [closed]

Suppose you have a prime $p$ (not necessarily odd) and you have $\tau$ defined by $p^\tau \| k$ for some integer $k$. Then you define \begin{equation} y = \begin{cases} \tau + 1 &, p > 2 \...
5
votes
0answers
192 views

Cardinality of the image of a polynomial modulo $p^n$

Let $f \in \mathbb{Z}[x]$ be a nonconstant polynomial and let $p$ be a prime number. I'm looking for results about $$N_f(p^k) := \#\{(f(n) \bmod p^k) : n \in \mathbb{Z}\},$$ as $k \to +\infty$, where $...
1
vote
0answers
186 views

Presentation of amalgamated sum as a quotient of the direct sum

I am currently reading Arthur Ogus' "Lectures on Logarithmic Algebraic Geometry" (https://math.berkeley.edu/~ogus/preprints/log_book/logbook.pdf). I'm trying to understand why the amalgamated sum of ...
6
votes
1answer
158 views

2-adic valuation of $L(0,\chi)$ for a Dirichlet character

Let $\chi : (\mathbb Z/f\mathbb Z)^\times \to K = \mathbb Q(\mu_{\phi(f)})$ be a primitive Dirichlet character. Assume moreover that it is not quadratic, that is, $\chi^2$ is not the trivial character....
1
vote
3answers
337 views

Finding a solution for this system of two diophantine equations (depending on a parameter) [closed]

I propose the following problem (Maybe it has a trivial solution): Let $n$ be a positive integer such that $$n\equiv1 \pmod 4.$$ Then the problem is to find a rational $x$ as a function of $n$ such ...