All Questions
49
questions
1
vote
0
answers
38
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,352
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
43
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
125
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,837
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
284
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.5k
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,025
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