Questions tagged [congruences]
The congruences tag has no usage guidance.
138 questions
5
votes
1
answer
430
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 ...
- 51
2
votes
1
answer
295
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
...
- 25.4k
11
votes
2
answers
1k
views
Ramanujan's tau function, $691$ congruence, and $\eta(z)^{12}$
Let $q = e^{2\pi i\,z}$.
I. 24th power
The Ramanujan tau function $\tau(n)$ is given by the expansion of the Dedekind eta function $\eta(z)$'s $\text{24th}$ power. Then
$$\begin{aligned}\eta(z)^{...
- 12.6k
4
votes
2
answers
616
views
Order of a matrix congruent to the identity modulo p
I couldn't find a demonstration of this theorem:
Given $A \in SO_2(\mathbb{Z}[{1 \over q_1},\dots,{1 \over q_k}])$
and $p$ prime $\notin \{q_1,\dots,q_k\}$
$\exists n \in \mathbb{N} : A^n=Id$ and $A\...
- 143
3
votes
1
answer
522
views
Solvability of Diophantine equation using congruences where the variables are bounded?
In page 2 of Mordell "Diophantion equations" it is given a necessary condition for the solvability of a Diophantine equation:
Integer solutions of the inhomogeneous equation $f(x) = 0$ can exist only ...
- 841
7
votes
2
answers
780
views
Some equalities involving prime powers
Let $p,a,b,x,y$ be positive integers where $p$ is an odd prime; $x$ and $y$ are odd; $p,x$ and $y$ are all coprime. I'm interested in finding examples of such numbers that satisfy this equation:
\...
- 11.2k
38
votes
4
answers
7k
views
What did Yu Jianchun discover about Carmichael numbers?
There's a news story going around (see for example [1]; other accounts are even more breathless) about an amateur mathematician, Yu Jianchun, finding an "alternative method to verify Carmichael ...
- 9,114
1
vote
0
answers
242
views
Computational number theory
Suppose that $p$ is prime and $q$ is an even number divides $p-1$, such that $q<\frac{p-1}{q}$ and $u$ has order $q$ modulo $p$. Let $S$ be the subgroup of $Z^*_p$ consisting of the powers of $u$. ...
2
votes
0
answers
178
views
Monoid prime ideals and prime congruences
I was wondering what the connection is between the notion of "prime congruence" on a monoid, and the notion of "prime ideal" in a monoid. Starting from a prime ideal $P$ in a monoid $M$, one can ...
- 4,547
4
votes
3
answers
544
views
On a theorem of Hensel about congruence of binomial coefficient
In the paper Binomial coefficients modulo prime powers, Andrew Granville stated the following theorem:
Let $n, m$ and $r=n-m$ be three given positive integer and $p^k$ is the exact power of $p$ ...
- 101
5
votes
1
answer
270
views
Up to $2000$, $A145722(n-1) \equiv \sigma(4n-3) \pmod{5}$
A145722 is
Expansion of f(q) * f(q^5) / phi(-q^2)^2 in powers of q where f(), phi() are Ramanujan theta functions.
Using the pari program and offset 0, up to $2000$...
- 25.4k
5
votes
1
answer
258
views
For a sufficiently large $a$, are there distinct (mod $a$) integers such that all powers up to the $n$-th are "close" modulo $a$?
Given $n\in\Bbb N$ is there an $a_n\in\Bbb N$ such that for every $a>a_n$ there are two distinct integers $0<b<c<a$ such that $b^i\bmod a,c^i\bmod a\in(\sqrt a,\sqrt a\log a)$ for every $i\...
- 13.9k
7
votes
1
answer
860
views
Is $n=6$ the only integer satisfies ${\sigma}_x(n) \equiv 0\bmod{n}$ for every odd integer $x > 0$ and $2 (\bmod n)$ if $x$ is even integer? [closed]
After a few computations in wolfram alpha about the divisor function for some values of $n$ to look the behavior of $\sigma_x(n)\bmod n$ for $\,n=6,\,$ i got this result : $\sigma_x(6)=0 \bmod 6$ for $...
- 414
13
votes
1
answer
1k
views
On cubic reciprocity for $x^3+y^3+z^3 = 996$?
I. The Diophantine equation,
$$x^3+y^3+z^3 = 3w^3\tag1$$
with $x\geq y \geq z$ and $w=1$ has only two known solutions, namely $1,1,1$ and $4,4,-5$. Are there larger ones? As Noam Elkies points out ...
- 12.6k
0
votes
0
answers
600
views
Systems of linear modular equations with unknowns in the moduli
I am interested in systems of linear modular equations, where the unknowns also appear in the moduli. The general form would be:
$A \vec{x}= \vec{b} \;\textrm{mod} \; (C \vec{x}+\vec{d})$
where A ...
- 940
4
votes
0
answers
182
views
Computing the density of a set of multiples
Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
- 9,114
10
votes
2
answers
1k
views
Is there a fixed integer $x>1$ satisfing ${\sigma}^{k}(x)\equiv 0\pmod{x}$ for all positive integers $k$?
This question related to this question from SE. I'm interested to know if there exists an integer $x>1$ that satisfies $${\sigma}^{k}(x)\equiv 0\pmod{x}$$
for all positive integers $k$.
Note. $\...
- 414
19
votes
2
answers
1k
views
A congruence involving binomial coefficients
The following open problem was shown to me by Maxim Kontsevich. I
state it in a different but equivalent form. Let $a(n)$ be the sequence
at http://oeis.org/A131868, that is,
$$ a(n) =\frac{1}{2n^2}\...
- 50.8k
3
votes
1
answer
585
views
Trying to prove a congruence for Stirling numbers of the second kind
This a repost of a question I asked at Stack Exchange, but I got no answer so far, so I am trying here, even though it may not suit the "research level" requirement.
Proposition: When $n$ and $m$ are ...
- 505
2
votes
1
answer
377
views
Cardinality of the prime divisor set of a k-power sum
Let $a_{1},\dots,a_{n}$ be positive natural numbers ($n>2$) such that $a_{i}\neq a_{j}$ if $i\neq j$. I want to prove that
$$ \left\lvert \left\{ p \text{ prime} \; : \; p \mid \sum_{i=1}^n a_{i}^{...
- 45
7
votes
1
answer
1k
views
Roots of a polynomial in a finite field related to Fermat's Last Theorem
In my class, we proved the following condition: define the polynomial $P_l(x)$ as
$$P_l(x) = \sum_{r=1}^{l-1}{\frac{1}{r}x^{l-1-r}}$$
Then if for all $a \in \mathbb{Z}/l\mathbb{Z}-\{0,1\},$ $P_l(x)$...
- 495
22
votes
1
answer
1k
views
Does $\binom{2n}{n} \equiv 2 \pmod p$ ever hold?
Well, the title does not tell the whole story; the complete question is:
Are there any primes of the form $p=2n(n-1)+1$, with integer $n\ge 1$, such that
$$ \binom{2n}{n} \equiv 2\pmod p ? $$
...
- 23k
11
votes
1
answer
625
views
A congruence conjecture regarding $(r-s)^4-1 \equiv 0\!\pmod{4r^2s}$
Is the following conjecture true?
Conjecture. If $r > s \ge 1$ are relatively prime integers such that
\begin{equation}
(r-s)^4-1 \equiv 0\!\pmod{4r^2s}, \tag{1}
\end{equation}
then $r-s = 1$ ...
- 1,055
0
votes
2
answers
470
views
What are all positive integers n for which the congruence $a^{n+1} \equiv a (mod n)$ holds? [closed]
Fermat's little theorem says that the congruence $a^p \equiv a (mod p)$ if $p$ is a prime number. $a^{n+1} \equiv a (mod n)$ works for all integers $a$ and some positive integers $n$, how can we ...
- 17
1
vote
0
answers
63
views
"embedding" various matrix equivalences into the equivalence of particular linear map
Consider the square matrices over a (local) ring $R$, up to conjugation, $A\rightarrow UAU^{-1}$, where $U$ is an invertible matrix over $R$. Such an equivalence embeds into the "left-right" ...
- 2,232
2
votes
1
answer
267
views
Does the congruence $a^p \equiv 1 \pmod{b^p}$ with prime $p \ge 5$ force $b \le p$?
I'm considering the congruence in the title, i.e.,
$$a^p \equiv 1 \pmod{b^p},$$
where $a \ge b \ge 1$ are positive integers and $p$ is an odd prime.
For $p=3$, a brute-force computer search found ...
- 1,055
6
votes
2
answers
245
views
Congruence equation for Apery numbers
Does the system of congruence equations
\begin{eqnarray}
A_{17k}&\equiv& 0 \pmod {17^2}, \nonumber \\
A_{17k+1}&\equiv& 0 \pmod {17^2}, \tag{1}
\end{eqnarray}
has solutions other ...
- 16.5k
9
votes
0
answers
315
views
congruences of level 1 and level p modular forms
I've been carrying out some experiments on the computer and I noticed the following congruence phenomenon: fixing a prime $p$, it seems that any modular form over $SL_2(\mathbb{Z})$ and of weight $k \...
- 597
-1
votes
1
answer
815
views
how to solve system of congruence with multivariables [closed]
There n variables x1,x2,...,xn represented as X, n equations whose coefficient matrix (n*n) is represented as A, and this system ...
- 1
0
votes
0
answers
407
views
Solutions to a quadratic congruence
Fix an odd prime $p$. Let $\alpha = (\alpha_0,\dots,\alpha_k)$ be a solution to the congruence $\sum_{i=0}^{k} \alpha_i^2 \equiv x \mod p$. Now consider the number $N_\alpha$ of solutions to the ...
- 1
1
vote
2
answers
185
views
Number of solutions to $mx^2+ny^2 \equiv k\pmod{p}$
I need a reference for the result which gives the number of solutions to the congruence $mx^2+ny^2 \equiv k\pmod{p}$. This result seems to be something that would be discussed in Gauss' ...
- 11
2
votes
1
answer
268
views
perfect shuffle of 2n cards
permutation is given by f(i) = 2i if i<=n and 2(i-n)-1 if i>n
where i denotes the position of cards.
eg pack of cards (1,2,3,4)-->(3,1,4,2)
Basically trying to find the multiplicative order of 2 ...
- 121
22
votes
0
answers
1k
views
Given a lattice L with n elements, are there finite groups H < G such that L $\cong$ the lattice of subgroups between H and G?
If there is no restriction on $n$, this is a famous open problem. I'm wondering if any recent work has been done for small $n>6$. I believe the question is answered (positively) for $n=6$ by ...
- 1,241
2
votes
0
answers
488
views
An elementary question in modular arithmetic
Let us fix a positive natural number $N$. When $i$ is a natural number smaller than $N$, coprime with $N$, we let $\mu(i)$ be the unique number in $\{1, \ldots, N-1\}$ that is the multiplicative ...
- 21
6
votes
3
answers
2k
views
Finite subgroup of $Gl(n,\mathbb Z)$ and congruences
Suppose we have an invertible matrix q in a finite subgroup $Q$ of
$Gl(n,\mathbb Z)$, the group of all invertible integer matrices. Now I want to
find all $x\; mod\; \mathbb Z^n$ for which
$(q+q^2+q^...
2
votes
2
answers
490
views
Proving Congruence Without Leech Lattice
Let $\sigma_{11}(n)$ denote the sum of the 11th powers of the positive integral divisors of the positive integer n.
Let $\tau(n)$ denote Ramanujan's tau function, which is the coefficient of $q^n$ in ...
- 3,645
2
votes
4
answers
4k
views
Best way to introduce the Chinese Remainder Theorem (to a high school student)
What do you think to be the most effective way to teach the Chinese remainder theorem to a smart high school student, which is supposed to only have a soft idea about how modular arithmetic works, and ...
- 1,269
18
votes
2
answers
3k
views
Binomial supercongruences: is there any reason for them?
One of the recent questions, in fact
the answer
to it, reminded me about the binomial sequence
$$
a_n=\sum_{k=0}^n{\binom{n}{k}}^2{\binom{n+k}{k}}^2,
\qquad n=0,1,2,\dots,
$$
of the Apéry ...
- 13.5k