1
vote
0answers
7 views

If there is a subset with sum divisible by n, then take out an integer of the subset. How many moves?

Fix an integer $n \ge 2$. A finite set $A \subset \mathbb{N} $ is given. Define $ s(X) = \sum_X x $, where $ X $ is a finite set. We know that $n \mid s(A)$. We can do just one move: if there is a ...
3
votes
0answers
48 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
0
votes
1answer
45 views

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd.

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd. This is a problem from ISI 2014 written test in a little ...
2
votes
0answers
33 views

Given any integers $a,b,c$ and any prime $p$ not a divisor of $ab$, prove that $ax^2+by^2\equiv c\pmod{p}$ is always solvable.

The fact that there are $\dfrac{p+1}{2}$ quadratic residues seem to me to help solving the question, but I don't know how to go on from that point. Could you give me any hint?
2
votes
1answer
72 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014. I like thinking about this problem, it is ...
1
vote
1answer
30 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics experts

We have some attempt to numerically solve this math problem, which means that we like to count the number of independent solutions of this set of six of modular N algebraic equations: $$ (1) x_1 ...
2
votes
2answers
46 views

$2^n$ modulo n where n is odd always yields either an even or $1$

I'm attempting to do a pidgeonhole proof to prove that for some odd integer n, there is always a $2^k$ such that $2^k \mod(n) = 1$. I know that $2^n \mod(n)$ will always yield either an even number or ...
1
vote
1answer
85 views

Minimum number of rows in a mod 12 multiplication table

Minimum number of rows you would need to write out in a mod 12 multiplication table to guarantee you wrote out an element with an inverse? I would think this would be just one row as 1 is its own ...
0
votes
1answer
41 views

Combinatorics and Linear Alegbra

$$T = \{1011, 0112, 2101\} \subset Z_3^4$$ Is there any efficient way to find the span for set T other than checking all 27 possibility? If so, how to do it?
6
votes
1answer
94 views

Rooks on a labeled chessboard

An $n\times n$ chessboard is constructed such that the coordinate $(i, j)$ is labeled with $i+j \mod n$. Example for n = 6: The goal is place $n$ rooks in the chessboard such that none threaten ...
14
votes
2answers
365 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 ...
5
votes
4answers
119 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$.
3
votes
0answers
87 views

Equivalence classes of triplets satisfying $x^2+y^2+z^2=0$ over $\mathbb{F}_p$

The affirmative answer to this question illustrates that the equation $$x^2+y^2+z^2=0$$ has $p^2-1$ nontrivial solutions over $\mathbb{F}_p$ (solutions that are not $(0,0,0)$). If $(x,y,z)$ is a ...
1
vote
0answers
352 views

Binomial coefficient modulo prime power without generalized Lucas theorem

I've been working on this problem computing $n \choose r$ for large $n$ and $r$, modulo a composite. I could implement the generalized lucas theorem to handle the prime power case, but I want to ...
0
votes
0answers
75 views

Distribution of binary digits in moduli

Considering the (infinite) set of all positive integers that are a product of $2$ primes only, represented in binary $100...01$. Question: is the distribution of the proportion of $0,1$ digits ...
1
vote
2answers
256 views

Function with a Modular Inverse

For a combinatorics problem I have a function, $h(x)$ that is always divisible by five, but it is calculated in pieces, e.g. $h(1) = 43 + 7$. The final function that I need is $f(x) = (h(x) / 5) ...
2
votes
2answers
93 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 ...
0
votes
2answers
132 views

$k$ hands in $n$'s hair

Moderator Message: this question is from an ongoing competition. Define a prime $p$ as having $k$ hands in $n$'s hair if $p^k|n$ and $n|2^n+1$ . Does there exist an integer $n$ with $2012$ hands ...
2
votes
0answers
200 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 ...
1
vote
2answers
116 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\ ...
4
votes
1answer
201 views

Fermat's little theorem for $n=3$

for $N > 0$, I'm trying to show Fermat's little theorem, for $3$ using the orbit stabilizer theorem: $N^3 - N$ an element of $3\mathbb{Z}\ (3 \mod \mathbb{Z})$ Pf/ we can break it down into ...
0
votes
3answers
67 views

Prove how many distinct elements in the set $\{ax \pmod{m}:a\in\{0,…,m-1\}\}$

There are $\dfrac{m}{\gcd(m,x)}$ distinct elements in the set $\{ax \pmod{m}:a\in\{0,...,m-1\}\}$ I have only known these by using a computer to generate the number of distinct elements. But I am not ...
6
votes
4answers
1k views

calculating n choose k mod one million

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $$ {n\choose k} = {n\choose k-1} \frac{n-k+1}{k} $$ so I don't have to calculate huge ...