# Questions tagged [elementary-number-theory]

Questions on congruences, linear Diophantine equations, greatest common divisor, divisibility, etc.

3,899 questions
4k views

31k views

### The product of $n$ consecutive integers is divisible by $n$ factorial

How can we prove that the product of $n$ consecutive integers is divisible by $n$ factorial? Note: In this subsequent question and the comments here the OP has clarified that he seeks a proof that "...
681 views

2k views

### Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$?

If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically ...
520 views

### Solving $ax \equiv c \pmod b$ efficiently when $a,b$ are not coprime

I know how to compute modular multiplicative inverses for co-prime variables $a$ and $b$, but is there an efficient method for computing variable $x$ where $x < b$ and $a$ and $b$ are not co-prime, ...
5k views

### A natural number multiplied by some integer results in a number with only ones and zeros

I recently solved a problem, which says that, A positive integer can be multiplied with another integer resulting in a positive integer that is composed only of one and zero as digits. How can I ...
14k views

### Proof: How many digits does a number have? $\lfloor \log_{10} n \rfloor +1$

I read recently that you can find the number of digits in a number through the formula $\lfloor \log_{10} n \rfloor +1$ What's the logic behind this rather what's the proof?
10k views

### Prove that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime [Wilson's Theorem]

How can I show that $(n-1)!$ is congruent to $-1 \pmod{n}$ if and only if $n$ is prime? Thanks.
3k views

### On the factorial equations $A! B! =C!$ and $A!B!C! = D!$

I was playing around with hypergeometric probabilities when I wound myself calculating the binomial coefficient $\binom{10}{3}$. I used the definition, and calculating in my head, I simplified to this ...
1k views

### Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

I can't crack this one. Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that $a,b,c,z \in \mathbb{Z}$).
### Prove that if $\gcd( a, b ) = 1$ then $\gcd( ac, b ) = \gcd( c, b )$
I know it might be too easy for you guys here. I'm practicing some problems in the textbook, but this one really drove me crazy. From $\gcd( a, b ) = 1$, I have $ax + by = 1$, where should I go from ...