# Questions tagged [divisibility]

This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

4,994 questions
Filter by
Sorted by
Tagged with
74 views

### If $a\mid b$ and $a>0$ then $(a,b)=a$

Now let $d=(a,b)$. So $d=ax+by$. Since $a\mid b$ , so we have $aq=b$, where $q \in \mathbb{Z}$. so we have $d=ax+aqy$. since a divides R.H.S , so it must divide L.H.S. So $a\mid d$ Also $d\mid a$ as ...
891 views

### Bit representation and divisibility by 3

I was reading about how to know if a number is divisible by 3 given binary representation of the number. After googling a bit I read a statement and I am puzzled how is this correct. we have to ...
116 views

### Given a positive integer $t$ does there always exist a natural number $k$ such that $(k!)^2$ is a factor of $(2k-t)!$?

For all natural numbers $k$ the ratio $$\frac{(2k)!}{(k!)^2}=\binom{2k}k$$ is an integer. From staring at the Pascal triangle long and hard, we know that these ratios grow rather quickly as $k$ ...
404 views

### Some Pythagorean triples proofs

I'm studying about number theory by myself. So I'm sorry if the question seems to be unclear. I just want to know how to prove that one member of a Pythagorean triple is always divisible by 5 and ...
90 views

### Find all positive integers which are representable uniquely as $\frac{x^2+y}{xy+1}$ with $x,y$ positive integers.

$\textbf{Question:}$ Find all positive integers,which are representable uniquely as $$\frac{x^2+y}{xy+1}\,,$$ where $x$ and $y$ are positive integers. I think this question maybe has something to do ...
37 views

### Is this a valid proof for checking if a number K is dividable by 11,

let s = $a_{0}+a_{1}+......+a_{n}$ let k = $a_{0}+a_{1}*10^{1}+......+a_{n}*10^{n}$ k-s = $a_{1}*(9_{1})+a_{2}*(9_{1}9_{2})+......+a_{n}*(9_{1}9_{2}....9_{n})$ It is obvious that 11 will divide any ...
67 views

### Find smallest $x$ such that $\gcd(a + x, b + x) = c$.

I need to find the smallest $x$ such that $$\gcd(a + x, b + x) = c$$ where $a, b, c, x$ are positive integers and $a \le b$. I was able to rewrite it as $$\gcd(a + x, b - a) = c$$ This shows that $c$ ...
37k 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 "...
57 views

### Proof of the Division Theorem (for all $a \in Z, b\in Z^+$, there exists $q,r\in Z$ such that $a=bq+r$ and $0\leq r\lt b$)

I've been asked to prove the division theorem (for all $a \in Z, b\in Z^+$, there exists $q,r\in Z$ such that $a=bq+r$ and $0\leq r <b$). There are many proofs on SE, and the web, however I have ...
34 views

55 views

### Prove the statements.

Prove that, f(x)=0 when k is not prime f(x)=1 when k is prime N.B: Here f(x)= a mod k means the reminder we get by dividing 'a' by 'k' I found that the statements are right by testing those. But I ...
102 views

138 views

### Suppose each of the numbers $a_1,\dots,a_n$ is either $1$ or $-1$ and $S=a_1a_2a_3a_4+a_2a_3a_4a_5+\dots+a_na_1a_2a_3=0$. Prove that $4|n$ [closed]

Here is the problem Suppose each of the numbers $a_1,\dots,a_n$ is either $1$ or $-1$ and $S=a_1a_2a_3a_4+a_2a_3a_4a_5+\dots+a_na_1a_2a_3=0$. Prove that $4|n$ Could someone help me with this problem?...
27 views

### Question on binomial expansion - divisibility by power of divisor

By the Binomial theorem, one has that $$(a+b)^n = a^n + \binom{n}{1} \ a^{n-1}b + \binom{n}{2}\ a^{n-2}b^2 + \dots + b^n$$ Let us suppose that $d\mid (a+b)$, where $\mid$ means "divides", ...
85 views

### Prove by mathematical induction, that $81\times 3^{2n} - 2^{2n}$ is divisible by $5$ where $n \in \mathbb{Z}^+$

For all $k$, the equation I came up with is $3^{4+2k} = 5m + 2^{2k}$ where $m$ is a positive integer. For all $k+1$, the expression is $3^{6+2k} - 2^{2k+2}$. I tried to plug in the first equation to ...
87 views

43 views

### Pythagorean triplets which satisfy the prime counting function $\omega(n)$

Let $\omega(n)$ be the number of prime factor of $n$. Out of the first $9.2 \times 10^9$ Pythagorean triplets $a^2 + b^2 = c^2$ (in ascending order of the hypotenuse) I found about $1.03 \times 10^7$ ...
149 views

### About the characterization of solutions of an equation that involves particular values of the Dedekind psi function

In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. This is an important arithmetic fuction in several subjects of mathematics. As reference I add the Wikipedia ...
84 views

### Is the equation $x = \phi(n), x=2k, n,k \in \mathbb{Z}$, where $\phi(n)$ is the Euler totient function, solvable for all evens?

I was just getting my hands dirty solving some equations of the form $x=\phi(n)$ where $\phi(n)$ is Euler totient function. I know that $\phi(n)$ is even for $n\geq 3$. However, I am wondering that: ...
31 views

### If $\gcd(a,p)=1$, $p$ is prime, prove that there are $1\le x, y\le [\sqrt p]$ that $ax≡y\pmod p$ or $ax≡-y\pmod p$

If $\gcd(a,p)=1$, $p$ is prime, prove that there are $1\le x, y\le [\sqrt p]$ that $ax≡y\pmod p$ or $ax≡-y\pmod p$ I met this when looking proof of theory which says if $p=4k+1$ then there are $a,b$ ...
78 views

### Proving that if $xo + yp = 1$, then $\gcd(o,p) = 1\;$?

I'm currently trying to prove the equation that you see above. I know that it must have something to do with the laws of divisibility, and these rules in conjunction with rules about integers, but ...
25 views

### prove that for all $n≥2$ $n^4+4^n$ is not prime [duplicate]

Prove that $4^n+n^4$ is not prime for $n≥2$. I've found if $n≠5k$ then $5$ divides all equation. We get it from residues when divided by $5$. Also it’s clear that if $n=2k$ then equation is not prime ...
99 views

### Use induction to prove 8 divides $7^n+3^n−2$ for all positive integers n. [duplicate]

I can't seem to simplify the problem down to $8m$, which makes it divisible by 8. Can anyone help me out and tell where I made a mistake, or if there's another way to solve this. Thanks, new user here ...
104 views

### Divisibility induction proof: $8\mid 7^n+3^n-2$

I'm stuck on the following proof by induction: $$8\mid3^n +7^n -2$$ And this is how far I've gotten: \begin{aligned}3&\cdot3^n+7\cdot7^n-2\\3&(3^n+7^n-2)+7^n(7-3)-2\end{aligned} Any help ...
50 views

### Using quadratic residues and/or reciprocity to prove relative primality?

I have odd positive integers $q$ and $y$, with $3q^2 < y^2 < 4q^2$, such that the following are true: \begin{align} (q^2+9) &\mid (y^2+5)(y^2+29) \\[0.25em] (q^2+2) &\mid (y^2+1)(y^...
53 views

### For how many natural numbers(<=100) is $1111^n +2222^n+3333^n+4444^n$ divisible by 10?

For how many natural numbers (0 not included) $n \leq 100$ is $1111^n +2222^n+3333^n+4444^n$ divisible by 10? I factored out $1111^n$ and got $1111^n(1+2^n+3^n+4^n)$. So $1+2^n+3^n+4^n$ must be ...
43 views

### How to simplify a fraction that has matrix

Recently, I was studying about optimum beamforming in array signal processing. In it, the maximum output SINR is $$SINR=\frac{W^{H}R_sW}{W^{H}R_{i+n}W}$$ and\quad W=R_{i+n}^{-1}a \quad R_s=\alpha^...
62 views

### Divisibility Number Theory problem, explanation needed

I can't understand the solution of the following problem: $x$,$y$,$z$ are pairwise distinct natural numbers show that $(x-y)^5$ + $(y-z)^5$ + $(z-x)^5$ is divisible by $5(x-y)(y-z)(z-x)$. No need to ...
44 views

### Answers to these problems in elementary number theory [duplicate]

Let $d,n \in \mathbb{N}$. Show that if $𝑑\mid 𝑛$ then $2^𝑑 − 1 \mid 2^n-1$ Hence show that $2^{25} − 1$ is divisible by $31$ and $127$.
122 views

### Triangular numbers divisible by $3$

I can't understand any of sentences from the images below. Since I don't understand almost every possible lines, I'm very troubled for what I should even ask. But I'll try to. Firstly, how is it ...
44 views

### On the equation $\psi(-1+2(\psi(n)-n))=n$ involving the Dedekind psi function, as a characterization of Mersenne primes

In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. This is an important arithmetic fuction in several subjects of mathematics. As reference I add the Wikipedia ...
61 views

### Proving that $k|(n^k-n)$ for prime $k$

Prove that for any integer $n$,we have $(n^k)- n$ is divisible by $k$ for $k=3,5,7,11,13$ I tried using prime factorization but that does not work here
44 views

### Question about divisibility rule by 7 explanation

So I just remembered a question I had a while ago about an explanation of the divisibility by 7 trick where you double the last digit and subtract it from the rest of the number. I think the ...
### Showing that a $3^n$ digit number whose digits are all equal is divisible by $3^n$
Let $c$ be a $3^n$ digit number whose digits are all equal. Show that $3^n$ divides $c$. I have no idea how to solve these types of problems. Can anybody help me please?