All Questions
49
questions
1
vote
0
answers
39
views
Counting solution to congruences
I want to count the $x, y \mod a$ and $r, s \mod b$ subject to the following conditions (defining $u, v, w, k$ which exist by the coprimality conditions)
$$(a, x, y) = 1$$
$$(b, r, s) = 1$$
$$ as+xr+...
- 1,285
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
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
0
votes
0
answers
44
views
How many musical notes does a scale need such that any integer intervals can be found in this scale?
We know that in the 12-tone equal temperament musical system, each octave is equally divided into 12 semitones. In a major scale, for example the C major scale, the notes are C, D, E, F, G, A, and B, ...
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
2
votes
0
answers
224
views
Number of quadratic congruences modulo $n$ having exactly $k$ solutions
Given integers $n$ and $k$, find the number of quadratic congruences of the form $$ ax^2 + bx + c \equiv 0 \pmod{n} $$ having exactly $k$ solutions in $\mathbb{Z}_n$, where $a, b, c \in \mathbb{Z}_n$....
- 277
2
votes
1
answer
502
views
Residues of powers modulo a squarefree integer
The following is an idle question on powers modulo composites. I find it natural and have no clue how to answer it. I am a beginning undergraduate, please include as many details as possible.
Setting :...
- 747
1
vote
3
answers
117
views
${p^k \choose p^{k-1}} \neq 0 \pmod {p^k}$
I would like to show ${p^k \choose p^{k-1}} \neq 0 \pmod{p^k}$, where $p$ is a prime and $k >1$. I think this is a rather obvious results and I cannot seem to prove it unfortunately. I have looked ...
- 1,106
0
votes
0
answers
69
views
Probability in sum and product of integer numbers
Let $p$ be a prime number.
(a) What is the probability that the sum of $p$ non-negative integers is divisible by $p$?
(b) What is the probability that the product of $p$ non-negative integers is ...
- 257
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
3
votes
0
answers
86
views
Given $n\in\mathbb{N}_{\geqslant 2}$, find the partition $(a_1,...,a_k)\in\mathbb{N}^k:\sum_{i=1}^k a_i=n$ of $n$ that maximizes $\prod_{i=1}^k a_i$
I am a solving programming question in Leetcode in which, given a number $n \in \mathbb{N}_{\geqslant 2}$, I have to find $(a_1, ..., a_k) \in \mathbb{N}^k$ such that $k \in \mathbb{N}$, $2 \leqslant ...
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
0
votes
1
answer
136
views
Golomb Rulers and Sets with Unique Sums
A set of integers ${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}}$ where ${\displaystyle a_{1}<a_{2}<...<a_{m}}$ is a Golomb ruler if and only if
$$
\text{for all }
i,j,k,l \in \{1,2,...,m\}
{\...
- 18.6k
0
votes
1
answer
98
views
How do I prove this modulo relation?
Any suggestions for a better title would be greatly appreciated.
This is related to a Codeforces problem for modulo arithmetic.
Given an array of non-negative positive integers:
$[a_1, a_2, \dots, ...
- 1,035
1
vote
0
answers
21
views
Solving two simultaneous modular equations for a maximum case solution
Consider two sets of numbers.
$E_1=\{1,1,-1,...\}$
$E_2=\{1,-1,-1,...\}$
Let the number of elements in $E_1$ be $n_1$ and the number of elements in $E_2$ be $n_2$. The number of 1's and -1's in ...
- 43
2
votes
1
answer
365
views
Efficient computation of $\sum_{i=1}^{i=\left \lfloor {\sqrt{N}} \right \rfloor}\left \lfloor \frac{N}{i^{2}} \right \rfloor$
I have tried to find a closed form but did not succeed but is there an efficient way to calculate the following expression
$\sum_{i=1}^{i=\left \lfloor {\sqrt{N}} \right \rfloor}\left \lfloor \frac{N}...
- 37
1
vote
1
answer
76
views
Number of $n$-element strings whose product of elements is congruent to 0 modulo $d$
Let us consider the $n$-element strings in the form $q_1 q_2 \dots q_n$, where $q_i$ is an integer in $\{0,1,\dots,d-1\}$ $\forall i$. These strings are in total $d^n$.
How many strings are such ...
- 13
1
vote
0
answers
89
views
Minimum number of rotation of tuples such that all first terms of the tuples are non zero
Let $K_n$ be an $n$-tuple with elements as the first n non negative numbers. For example $K_5$ can be $(2,3,1,4,0)$.
Let a "shift" be a rotation in the tuple, i.e. after a "shift" the $K_5$ from ...
- 691
1
vote
0
answers
180
views
Find integer $n$ modulo composite.
Suppose we want to find a positive integer $n < M$ where $M$ is a constant value of which we know a good approximation.
For every prime $p$, an oracle gives us a set $B_p$ of residuals modulo $p$ ...
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
3
votes
0
answers
98
views
For the set $ S=\{0, 1, 2, ...., n-1\}$, count the number of times that $(n) \vert (ab-cd)$
I've been looking at how zero divisors of 2x2 matrices behave with modular arithmetic, and I've come upon an interesting pattern that I am trying to better understand. Essentially, I'm looking for a ...
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
1
vote
2
answers
707
views
No. of ways for $(((n \mod i) \mod j) \mod k) \mod n$
Consider $3$ integers, $i, j, k$ all between $1$ and $m$, both exclusive. Consider
$$(((n \mod i)\mod j)\mod k)\mod n$$
where $n$ is another positive integer. Suppose the maximum value of the above ...
- 41
2
votes
0
answers
49
views
In how many ways can I decompose $n \equiv \pm k \mod{m}$ in a sum of numbers also congruent to $\pm k \mod m$?
I'm trying to quantify the solutions for the following problem:
Given a large $n$ and a small number $m$ such that $n \equiv \pm k \mod{m}$, what is the number of ways I can decompose $n$ on a sum of ...
- 1,307
2
votes
1
answer
58
views
Modular arithmetic: Reaching an interval
Given $n=2^w$, where $w$ is the word length.
Consider an interval $[c_1,c_2]$, where $0\leq c_1,c_2\leq 2^w-1$, and let the interval length be $d$. Also, consider an operation $+\delta$, where $0\...
- 93
2
votes
0
answers
358
views
Combinatorical method proving Euler's theorem
If this a duplicate question than I apologize.
How would you prove Euler's theorem using combinatorics? The theorem goes:
$x^{\phi(n)}\equiv 1 \pmod n$ where $(x, n)=1$
I can only come up with ...
user482578
1
vote
3
answers
235
views
Struggling with the proof of Fermat's little theorem
I am working through Dirichlet's proof of Fermat's little theorem.
I am at the stage where I am trying to prove that:
$(a, 2a, 3a, ..., (p-1)a) \mod p$ is a rearrangement of $1,2,3..., p-1$.
In the ...
- 141
2
votes
0
answers
379
views
What is the probability that two random vectors in $\mathbb{Z}_n^k$ have dot product $z$?
In particular, I'm considering the set
$S(n, k, z) = \{(x, y) \in (\mathbb{Z}_n^k)^2 \mid \langle x, y \rangle = z\}$
which contains, for any $n, k, z$ each pair of vectors $(x, y) \in (\mathbb{Z}_n^...
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
3
votes
0
answers
41
views
Counting coefficients of linear congruences with prescribed solution
Let $p$ be any prime. Let $m,n$ be positive integers with $\frac{3}{2}m < n < 2m$. Let $x$ be a positive integer with $1 \leq x < p^n$ and $\gcd(x,p)=1$.
Let $A = \{ a \in \mathbb{Z} : 1 \...
- 1,533
3
votes
0
answers
179
views
Transformation of $e^{2\pi i z}$.
I want to find the use of $q=e^{2\pi i z}$ in modular forms and combinatorics.
The question here maybe a little not specific,
and I'll explain it.
I know that this is a exponential map，and map upper ...
- 641
1
vote
1
answer
172
views
number of different kinds of partitions of $n$ are the same
I want to prove that:
The number of partitions of $n$ into parts congruent to $1$ or $5$ ($\text{mod}$ 6) equals number of partitions of $n$ into distinct parts all congruent to $1$ or $2$ ($\text{...
- 267
3
votes
1
answer
169
views
$1\cdot3\cdot5 \cdots (p - 2) = (-1)^{m+k+1} \pmod p$, and $2\cdot4\cdot6\cdots(p - 1) = ( -1)^{m +k} \pmod p$.
Prove that if $p$ is a prime having the form $4k + 3$, and if $m$ is the number of quadratic residues less than $\frac p2$, then we have
$$1\cdot3\cdot5 \cdots (p - 2) = (-1)^{m+k+1} \pmod p, \text{ ...
- 12.7k
1
vote
2
answers
198
views
number of $k$-subsets of an $n$ element set, where $k \equiv 1 \bmod 3$ [duplicate]
I would like to find the number of $k$-subsets of an $n$ element set, where $k \equiv 1\bmod 3$.
We can consider the set $[n]=\{1,2, \ldots, n\}$. The number I am looking for would be
$$\sum_{j\geq ...
- 267
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
0
votes
1
answer
642
views
Trailing zeroes in product of numbers with factorial power
I need to find the number of trailing zeroes in $1^{1!} \cdot 2^{2!} \cdot 3^{3!} \cdots N^{N!}$, where $N$ is natural number.
Assuming $N$ is very large, say $500$, where you cannot find factorial ...
- 235
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
1
vote
1
answer
200
views
Show that the sum of a run of integers is divisible by $n$
Here is the problem:
Let $a_1,a_2,...,a_n$ be integers. Show that there exist integers $k$ and $r$ such that the sum $$a_k+a_{k+1}+...+a_{k+r}$$ is divisible by $n$.
My thoughts: I suppose we have ...
- 4,510
-1
votes
1
answer
62
views
Counting number of functions in modular arithmetic
$ f(kx \mod p) \equiv kf(x) \mod p$ for some function $f$ defined as $f: \{0,1,....p-1\} \rightarrow \{0,1,....p-1\} $, where $p$ is an odd prime and $k$ lies in the range $[0,p-1]$ (both $p$ and $k$ ...
- 31
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
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
3
votes
2
answers
52
views
Number of elements of $\mathbb{Z}_p$ that satisfy a certain property
Let $S(n,p)=\{a\in \mathbb{Z}_p : a^n=1$ (mod $p$)$\}$ where $p\geq3$ is a prime number and $1\leq n\leq p$. I am interested in finding a general formula for cardinality of $S(n,p)$. For example, I ...
- 31
2
votes
1
answer
110
views
Number of answers of equation amongs odd natural numbers
How many answer The following Equation has, in set of odd natural numbers?
$x_1+x_2+...+x_k=n$, $k \equiv^2 n$
Solution: Comb ( [(n+k)/2]-1, k-1), comb means combination. how we get this?
- 324
2
votes
2
answers
237
views
Formula for the number of solutions of the congruence equation $xy-wz=0$ over $\mathbb{Z}_p$?
The equation $xy-wz=0$ has 10 solutions over $\mathbb{Z}_2$ and 33 solutions over $\mathbb{Z}_3$ (e.g. $x=y=2 \land w=z=1$ is one of the solutions). Is there any formula for the number of solutions ...
- 21
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
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
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
2
votes
0
answers
848
views
$a^{(b^c)} \mod m$ where $c$ can be very very large
I am trying to solve the following problem.
I need to find the value of
$$
a^{(b^x)} \bmod m
$$
where $a,b$ are integers and
$$
x = \pmatrix{n\\0}^2 + \pmatrix{n\\1}^2 + ... + \pmatrix{n\\n}^2 ...
- 33
1
vote
2
answers
517
views
Solutions to $x_1+2x_2+3x_3+4x_4+5x_5+6x_6+7x_7+8x_8+9x_9+10x_{10}\equiv0\mod11$
How many solutions does the following equation have:
$x_1+2x_2+3x_3+4x_4+5x_5+6x_6+7x_7+8x_8+9x_9+10x_{10}\equiv0\mod11$
where
$x_{1...9} \in \{0,1,2,3,4\ ...\ 8,9\}$ and $x_{10}\in\{0,1,2,3,4\ ...\...
- 179