All Questions
49
questions
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