Articles of divisibility

The elegant expression in terms of gcd and lcm – algebra – (2)

Definition: suppose a quantity $P$ is identified by $$ \frac{P}{k}\simeq \frac{P}{k}+1 $$ what we mean is that $$ P= 0\pmod{k}. $$ That means that when $P \to P+k$, then $$ \frac{P}{k}\to \frac{P+k}{k}=\frac{P}{k}+1 = \frac{P}{k}+1 $$ This $\frac{P}{k}$ is identified as $\frac{P}{k}+1$. Challenge: Suppose a quantity R is identified by: $$ \frac{k_1 k_2}{k_{12}} R \simeq \frac{k_1 […]

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b;a^2+b^2)= 1$ or $2$.

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b,a^2+b^2)$ is always equal to either 1 or 2, where $\gcd$ is the greatest common divisor. I haven’t really ever solved a problem like this before, so I’d like to get some help. Thanks.

How to find all binary numbers in base $10$ s.t. that its divisible by its own numerical value in base $2$?

Consider $N=1010$. Its numerical value in base-$2$ is $2^3+2=10$ and $10 \mid 1010$. How to find all positive integers like $N$? Its easy to see that $n$ is in the form $10^{n_1}+10^{n_2}+…+10^{n_k}$, where $n_1>n_2>…>n_k \ge 0$. We need $$ 2^{n_1}+2^{n_2}+…+2^{n_k} \mid 10^{n_1}+10^{n_2}+…+10^{n_k} $$ I’ll be very grateful if you could share your thoughts on this […]

Proof that the euler totient function is multiplicative, correctness?

I’ve tried proving that $\varphi(mn) = \varphi(m)\varphi(n)$ (if $gcd(mn)=1$). The proof I try to setup doesn’t look like the proof I find in textbooks, where am I going wrong? Proof: We try to show that the number of relative primes to $mn$ in $\{1, 2, \ldots , mn-1\}$ is equal to the number of relative […]

Greatest common divisor of $3$ numbers

Let $a,b, c$ belong to $\mathbb Z$ such that $(a,b,c) \neq (0,0,0)$. Define the [highest common factor] greatest common divisor ${\rm gcd}(a, b, c)$ to be the largest positive integer that divides $a, b$, and $c$. Prove that there are integers $s, t, u$, such that $${\rm gcd}(a, b, c) = sa + tb + […]

Prove that $\frac{\binom{p}{k}}{p}$ is integral for $k\in \{1,..,p-1\}$ with $p$ a prime number with a particular method

This question already has an answer here: Proof: if $p$ is prime, and $0<k<p$ then $p$ divides $\binom pk$ [duplicate] 6 answers Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$ 5 answers

Proof for divisibility rule for palindromic integers

I am studying for a test and came across this in my practice materials. I can prove it simply for some individual cases, but I don’t know where to start to prove the full statement. Can you help me? Prove that every palindromic integer in base $k$ with an even number of digits is divisible […]

Conditions for which $n | {n \choose k}$ for all $k$

I’m studying for a number theory exam. Our review sheets offers the question: Under what conditions will $n$ divide $n \choose k$ for all 1 $ \leq k \leq n-1$? I can see that this will be true for any prime $n$, and don’t think that it would be true for any composite $n$, but […]

Prove by induction that $a-b|a^n-b^n$

This question already has an answer here: Why $a^n – b^n$ is divisible by $a-b$? 9 answers

For every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$

I’m trying to prove that for every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$. The first part of this bi-conditional was easy for me to prove, but I’m having problems with the second. Here is what I have so far: Suppose $15\mid n$. Then we can let $k$ be some integer such […]