All Questions
49
questions
32
votes
3
answers
5k
views
When is $\binom{n}{k}$ divisible by $n$?
Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
- 2,106
14
votes
0
answers
288
views
All interval sequences mod integers
In music, an all-interval twelve-tone sequence is a sequence that contains a row of 12 distinct notes such that it contains one instance of each interval within the octave, 1 through 11. The more ...
- 2,733
9
votes
2
answers
520
views
Expectation of $\min(a \bmod p,2a\bmod p,....,ka \bmod p)$
Given $k,p \in \mathbb N$, what's
$$
\mathbb E(\min(a \bmod p,2a\bmod p,...,ka \bmod p))
$$
where $a$ is a random integer in $[0,p)$?
According to the simulation, I found the answer is roughly $\...
- 5,054
8
votes
2
answers
435
views
$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?
From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
user228168
7
votes
1
answer
728
views
Counting pairs of squares in ${\mathbb Z}_n$ with certain distance
Let $S_n = \{ x^2 \pmod{n} \mid x \in \mathbb Z \}$ denote the set of squares in ${\mathbb Z}_n$.
Define $S_n(d) = \{ (x, y) \in S_n^2 \mid x + d \equiv y \pmod{n} \}$.
Is there an explicit formula ...
- 195
5
votes
4
answers
621
views
${{p-1}\choose{j}}\equiv(-1)^j \pmod p$ for prime $p$
Can anyone share a link to proof of this?
$${{p-1}\choose{j}}\equiv(-1)^j(\text{mod}\ p)$$ for prime $p$.
- 4,793
5
votes
1
answer
205
views
Conjecture: $\binom{n}{k } \mod m =0$ for all $k=1,2,3,\dots,n-1$ only when $m $ is a prime number and $n$ is a power of $m$
While playing with Pascal's triangle, I observed that $\binom{4}{k } \mod 2 =0$ for $k=1,2,3$,and $\binom{8}{k } \mod 2 =0$ for $k=1,2,3,4,5,6,7$ This made me curious about the values of $n>1$ and ...
- 6,581
5
votes
1
answer
151
views
Prove that the following congruence involving Lucas sequence is true
I am proving a congruence that appears in a paper, it claims that for $t\in\mathbb{Z}$ and prime $p\geq5$
$$p\sum_{k=1}^{p-1} \frac{t^k}{k^2\binom{2k}{k}}\equiv \frac{2-v_p(2-t)-t^p}{2p}-p^2\sum_{k=1}^...
- 515
4
votes
1
answer
126
views
can one select 102 17-element subsets of a 102-element set so that the intersection of any two of the subsets has at most 3 elements
Can one select 102 17-element subsets of a 102-element set so that the intersection of any two of the subsets has at most 3 elements?
I'm not sure how to approach this problem. I think it might be ...
- 1,835
4
votes
0
answers
251
views
Sum of even binomial coefficients modulo $p$, without complex numbers
Let $p$ be a prime where $-1$ is not a quadratic residue, (no solutions to $m^2 = -1$ in $p$).
I want to find an easily computable expression for
$$\sum_{k=0}^n {n \choose 2k} (-x)^k$$
modulo $p$. ...
- 4,284
3
votes
2
answers
91
views
How to find the remainder of $\binom{2013}{101}$ when it is divided by 101
I start first from the definition of
$$\binom{n}r=\frac{n!}{r!(n-r)!} $$
then I used the Wilson's theorem for p is prime
$$(p-1)!\equiv-1\pmod p$$
now how we can continue??
- 571
3
votes
3
answers
286
views
solutions to $\frac{1}a + \frac{1}b + \frac{1}c = \frac{1}{2018}$
Find, with proof, all ordered triplets of positive integers $(a,b,c)$ so that $\dfrac{1}a + \dfrac{1}b + \dfrac{1}c = \dfrac{1}{2018}.$
In general, if $d$ is a positive integer, then $(a,b,c) = (3d,...
- 1,166
3
votes
2
answers
166
views
Counting the number of matrices which cause collision
Let $m,n \in \mathbb{N}$, and $q$ be a prime number.
Let $\mathbf{A} \in \mathbb{Z}^{m \times n}_q$ be a matrix. In the following, assume that all additions and multiplications are performed modulo $...
- 3,331
3
votes
1
answer
171
views
$\binom{n}{k}$ modulo prime power for large $n$ and small $k$
I have to compute several value of $\binom{n}{k}$ mod $p^a$ for prime $p$ over a range of $k$, where $n$ is large and fixed, and $k$ is small and dynamic.
Is there a way to speed the process up? If I ...
- 1,161
3
votes
2
answers
183
views
Bernoulli Number Congruence
In a paper by L. Carlitz entitled A Property of the Bernoulli Numbers, it is written
The Bernoulli numbers may be defined by the symbolic relation $$(B+1)^n-B^n=0 $$ with $n>1$ and $B_0=1$, ...
- 8,837