# Questions tagged [divisibility]

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

5,045 questions
Filter by
Sorted by
Tagged with
782 views

### Understanding the proof of a formula for $p^e\Vert n!$

This is a proof from a book on number theory I'm reading. I'm having a hard time following. I think there's a variable here that means two different things at two different times... Theorem: If n is ...
1k views

### Formula To Determine Percentage Between Two Numbers After Certain Threshold

I have a formula I use to determine how opaque some validation text should be based upon the length of a user's input compared to the maximum lenth allowed. I want to modify it so that the "ramping ...
3k views

### What is the probability that 5 digit number divisible by 6?

The main constraint is that each digit can only take digits from $\{1, 2, 3, 4, 5\}$. So the sample space will be $5^{5}$. What is the probability that a random number taken from this sample space ...
6k views

### Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$. I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = gcd(...
3k views

### Showing that gcd does not exist for $3(1+\sqrt{-5})$ and $3(1-\sqrt{-5})$ in $\mathbb Z[\sqrt{-5}]$.

An exercise asks me to show that $3(1+\sqrt{-5})$ and $3(1-\sqrt{-5})$ have no greatest common divisor in $\mathbb Z[\sqrt{-5}]$. I think I have to find two maximal common divisors which are not ...
11k views

### How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$?

I am trying to prove that $\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$. The definition of GCD available to me is as follows: Given integers a and b, there is one and only one number d with the ...
205 views

### Interesting prime factorization function divisibility problem [duplicate]

Possible Duplicate: Is the set of all numbers which divide a specific function of their prime factors, infinite? Let the function $f(n) =(p_1^{a+1}-1)(p_2^{b+1}-1)...$ where $n$ is an integer ...
9k views

### Is “divisible by 15” the same as “divisible by 5 and divisible by 3”?

Is stating that a number $x$ is divisible by 15 the same as stating that $x$ is divisible by 5 and $x$ is divisible by 3?
3k views

### prove for all $n\geq 0$ that $3 \mid n^3+6n^2+11n+6$

I'm having some trouble with this question and can't really get how to prove this.. I have to prove $n^3+6n^2+11n+6$ is divisible by $3$ for all $n \geq 0$. I have tried doing $\dfrac{m}{3}=n$ and ...
818 views

### My attempt to prove GCD exists

Please review my attempt to prove a theorem. Any mistakes you point would be highly appreciated by me. To prove the theorem, I'll be using the following properties which I'm assuming have already ...
22k 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....
338 views

206 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 ...
735 views

832 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.
321 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 ...