# Questions tagged [divisibility]

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

4,985 questions
Filter by
Sorted by
Tagged with
21k views

### Are half of all numbers odd?

Plato puts the following words in Socrates' mouth in the Phaedo dialogue: I mean, for instance, the number three, and there are many other examples. Take the case of three; do you not think it may ...
2k views

### Simple divisibility proof $\ 2\mid a,\ 2^k\mid a(a+1)\,\Rightarrow\, 2^k\mid a$

Given integers $a$, $k$, and $n$, and given that $a(a+1)=n(2^k)$, how do I prove that (assuming $a$ is even), $2^k|a$? I read this in a proof, and I can't figure out how to verify it myself.
314 views

### Which Digit-Permutations Preserve Divisibility?

This is a completely random question that just happened to come to mind recently and I was wondering if the MathSE community had anything to say about it. Let $n > 1,b > 1$ be integers and ...
106 views

### How many pairs of natural solutions to $p^2q^2-4(p+q)=a^2$?

How shall I find all natural numbers p and q such that $$p^2q^2-4(p+q)=a^2$$ for some natural number $a$? Thanks!
253 views

### “If $m$ divides two Fermat numbers, $m$ divides $2$.” Why?

(A Fermat number $F_n$ is such that $F_n = 2^{2^n} + 1, \; \; n=0,1,2,3...$.) We will show that any two Fermat numbers are relatively prime; hence there must be infinitely many primes. We verify the ...
16k views

### Why $\gcd(qb+r,b)=\gcd(b,r)$?

Given: $a = qb + r$. Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so? Addendum by LePressentiment on 11/29/2013: (in the interest of http://meta.math....
333 views

203 views

### Prove that $2^n | P(2n, n)$

I am attempting to use Induction to prove this, but I am not sure if it is the right method to take. Here is what I have tried: Induction Hypothesis: Assume $P(k)$ is true for some fixed $k \geq 1$ ...
3k views

### Prove by induction: $2^n + 3^n -5^n$ is divisible by $3$

Let $P(n) = 2^n + 3^n - 5^n$. I want to prove that $P(n)$ is divisible by $3$ for all integers $n\geq 1$. The basis step for this proof is easy enough: $P(1)$ is divisible by $3$. For the ...
659 views

### If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$

How to prove that: If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$ This statement is generalization of the statement from my previous question. I have checked for many $(a,b)$ pairs ...
431 views

### If $\gcd(a,b)=1$ , and $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$?

How to prove that: $\gcd(a,b)=1 \Rightarrow \gcd(2^{a}+1,2^{b}+1)=1$ ,where $a$ is even and $b$ is odd natural number For example: $\gcd(2^8+1,2^{13}+1)=1 , \gcd(2^{64}+1,2^{73}+1)=1$ I know ...
733 views

828 views

### Leaving Cert Math Long Division

Solution to problem Hi, I'm correcting my work for study, and I cant get my head around this sum. I understand where the $x^2 + x − cx$ comes from but then when the 6 appears it loses me.
320 views

### Let $a\mid c$ and $b\mid c$ such that $\gcd(a,b)=1$, Show that $ab\mid c$

Let $a\mid c$ and $b\mid c$ such that greatest common divisor (gcd) $\gcd(a,b)=1$, Show that $ab\mid c$.
9k views

### Fibonacci divisibilty properties $F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$

Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...