Questions tagged [congruences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6
votes
0answers
155 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
64 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
160 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
71 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
76 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
124 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
147 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 ...
2
votes
0answers
129 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
194 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
172 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
45 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
108 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
117 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
185 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
74 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
129 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
257 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
267 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
56 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
0answers
225 views

A Wolstenholme type congruence

Consider the following congruence: For $p\geq 5$ prime and every $n,\nu\in\mathbb{N}$ we have \begin{align*} 0\equiv\sum_{k=1\atop p\nmid k}^{pn-1}\frac1k \binom{pn(\nu+1)-k-1}{pn\nu-1} \mod p^{2(\...
1
vote
1answer
79 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
163 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
874 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
0answers
246 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
332 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
331 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
162 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
231 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
188 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
224 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
63 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
352 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}$...
3
votes
0answers
166 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
174 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
154 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
150 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
335 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 ...
5
votes
4answers
337 views

When does the following congruence identity hold?

Let $m$,$l$ be coprime integers where $m,l\geq 2$. For any integer $a$ and positive base $b \ (b\geq 2)$, let $ [a]_b $ denote the element of $\{0,\ldots, b-1\}$ that satisfies the equivalence $[a]...
9
votes
2answers
247 views

For which values of $k$ is it known that there are infinitely many $n$, such that $2^{n+k}\equiv 1\pmod{n}$?

I know that there are no solutions to $2^n\equiv 1\pmod{n}$ for $n>1$ and I can prove that there are infinitely many $n$ such that $2^{n+1}\equiv1\pmod{n}$. My question is: Do we know other ...
12
votes
1answer
2k views

A good reference to the general Chinese Remainder Theorem

I am writing a paper on the topology of the Golomb space and need a good (standard) reference to the following General Chinese Remainder Theorem. For integer numbers $a_1,\dots,a_n$ and positive ...
2
votes
0answers
90 views

“Close” roots of polynomials and Pillai property

A sequence of integers $a(n)_{n \geq 0}$ has the Pillai property if there exists an integer $G \geq 2$ such that for all integers $k \geq G$ there exists an integer $n \geq 0$ such that none of the $k$...
35
votes
2answers
2k views

Is the sum of digits of $3^{1000}$ divisible by $7$?

Is the sum of digits of $3^{1000}$ a multiple of $7$? The sum of the digits of $3^{1000}$ can be computed using a computer. It is equal to $2142$, so the answer is positive. Is there a short proof ...
11
votes
2answers
298 views

Harmonic congruence

There are a number of interesting congruences for harmonic sums, not the least of which is Wolstenholme's theorem: $H_{p-1}:=\sum_{j=1}^{p-1}\frac1j\equiv 0\mod p^2$. It appears that $\sum_{j=1}^{p-1}...
4
votes
1answer
282 views

Matrix congruence

Let $A$ be an $n\times n$ matrix with integer entries and let $d_1,...,d_n|q$ all be given natural numbers (I am happy to assume that $q$ is a prime power). How many solutions $x_1,...,x_n$ modulo $q$...
3
votes
1answer
307 views

Probability in $GL_2(\mathbb{Z}/p^{r}\mathbb{Z})$

My question may be not interesting or easy to answer ! but I am really not familiar with proba. Let $p$ be an odd prime number. and let $r\geq1$ an integer. choose an element $A\in\mathrm{GL}_2(\...
1
vote
1answer
147 views

What is the general formula for $\# \{ 1 \leq a \leq q-2,| (a,q)=1, (a+2,q)=1 \}$

Let $q=\prod P_i^{k_i}.$ I have learned here that $\# \{ 1 \leq a \leq q-1| (a,q)=1, (a+1,q)=1 \}= F(q)=\prod (p_i-2)pi^{k_i-1} = q\prod (1-2/p_i)$ Here was the idea behind it : For any $p_i$, there ...
-2
votes
1answer
149 views

Solve an equation with a factorial [closed]

x! - 2 = y^2. Task: Solve over the naturals. I think the answers are x = 3, x = 2, but I am not sure.
5
votes
1answer
342 views

About Morley congruence

Let $p>3$ be an odd prime and $a$ be a positive integer, is the following congruence true? $$\binom{p^a-1}{\frac{p^a-1}{2}}\equiv(-1)^{\frac{p^a-1}{2}}4^{p^a-1}\pmod{p^3}.$$ When $a=1$, this is ...
2
votes
1answer
224 views

Efficiently lifting $a^2+b^2 \equiv c^2 \pmod{n}$ to coprime integers

Let $n$ be integer with unknown factorization. Assume factoring $n$ is inefficient. Let $a,b,c$ satisfy $a^2+b^2 \equiv c^2 \bmod{n}, 0 \le a,b,c \le n-1$. Is it possibly to lift the above ...