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+...
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 ...
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$. ...
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 ...
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$....
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 :...
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 ...
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 ...
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}^...
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,...
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\}
{\...
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
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 ...
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}...
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 ...
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 ...
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 $\...
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 ...
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 ...
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 ...
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\...
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 ...
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 ...
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 ...
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 \...