# Questions tagged [divisibility]

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

817 questions
Filter by
Sorted by
Tagged with
6k views

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....
4k views

### Divisibility criteria for $7,11,13,17,19$

A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for ...
1k views

### Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = \gcd(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$.

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = hcf(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$. We know that if $a|c$ and $b|c$ then $a\cdot b\cdot s=c$ (for some ...
52k views

### For any prime $p > 3$, why is $p^2-1$ always divisible by 24?

Let $p>3$ be a prime. Prove that $24 \mid p^2-1$. I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two ...
12k views

### $\gcd(a,b,c)=\gcd(\gcd(a,b),c)\,$ [GCD Associative Law]

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ for $0\ne a,b,c\in \Bbb{Z}$. I tried solving it with sets but I sense there are some details I am missing. I would truly appreciate your reference.
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 ...
8k views

36k views

### If $\gcd(a,b)=1$ and $a$ and $b$ divide $c$, then so does $ab$

Using divisibility theorems, prove that if $\gcd(a,b)=1$ and $a|c$ and $b|c$, then $ab|c$. This is pretty clear by UPF, but I'm having some trouble proving it using divisibility theorems. I was ...
48k views

### If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$

How do I go about proving this? If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$. I'm very confused with gcd proofs.
29k views

### If $\gcd(a,b)= 1$ and $a$ divides $bc$ then $a$ divides $c\$ [Euclid's Lemma]

Well I thought this is obvious. since $\gcd(a,b)=1$, then we have that $a\not\mid b$ AND $a\mid bc$. This implies that $a$ divides $c$. But apparently this is wrong. Help explain why this way is ...
17k views

### If $n\ne 4$ is composite, then $n$ divides $(n-1)!$.

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
9k views

### Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$

Somewhere on Stack Exchange I saw the equation $$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$ I had never seen this before, so I started trying to prove it. Without success... Can anyone explain me (so ...
5k views

### Derive a formula to find the number of trailing zeroes in $n!$ [duplicate]

Possible Duplicate: How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? I know that I have to find the number of factors of $5$'s, $25$'s, $125$'s etc....
1k views

### If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
17k views

6k views

### GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)

I was curious as to another method of proof for this: Given $a$, $b$, and $x$ are all natural numbers, $\gcd(ax,bx) = x \cdot \gcd(a,b)$ I'm confident I've found the method using a generic common ...
23k views

### Proof of $\gcd(a,b)=ax+by$

Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs? $a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be ...
3k views

### prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$
I'm trying to prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$ I showed that both $n,m$ divides $nm/\gcd(n,m)$ but I can't prove that it is the smallest number. Any help will be appreciated.
Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.