Questions tagged [divisibility]

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

Filter by
Sorted by
Tagged with
9
votes
6answers
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
14
votes
6answers
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(...
8
votes
2answers
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 ...
8
votes
4answers
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 ...
1
vote
1answer
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 ...
10
votes
2answers
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?
8
votes
9answers
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 ...
15
votes
1answer
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 ...
122
votes
8answers
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 ...
7
votes
4answers
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.
3
votes
3answers
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 ...
0
votes
1answer
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!
1
vote
2answers
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 ...
34
votes
8answers
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....
2
votes
2answers
338 views

Divisor of $m$ and $n$ divides $m - qn$ (in proof of Euclidean algorithm)

In Knuth's book "The Art Of Computer Programming Vol.1" there is a description about Euclid's algorithm to find the greatest common divisor of m and n. And there is a phrase. $m = qn+r$. If $r = ...
1
vote
1answer
82 views

Looking for references on results on powers of primes dividing $y^n-1$

For a prime $p$ and positive integer $n$, let $E(n,p)$ be the greatest $k$ such that $p^k \mid n$, and $E(n,p) = 0$ if $p \nmid n$. Let $E(n) = E(n, 2)$. A number of years back, I proved the ...
5
votes
7answers
12k views

Trick to find multiples mentally

We all know how to recognize numbers that are multiple of $2, 3, 4, 5$ (and other). Some other divisors are a bit more difficult to spot. I am thinking about $7$. A few months ago, I heard a simple ...
2
votes
2answers
537 views

Prove a property of divisor function

Let $n$ be a positive natural number whose prime factorization is $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_i$ are natural distinct prime numbers, and $a_i$ are positive natural numbers. ...
1
vote
0answers
207 views

Forcing and divisibility

I'm going to bring together a couple of seemingly unrelated questions that I've asked here. This may be silly. Or maybe not? Imagine that $n$ is some sort of infinitely large integer, and thus so ...
15
votes
2answers
693 views

How rare are the primes $p$ such that $p$ divides the sum of all primes less than $p$?

This is just for fun! The title pretty much says it all. It's probably a very difficult question. Up to the $40,000^{th}$ prime $(479909)$, I have found only $5$, $71$ and $369119$ with this property....
2
votes
1answer
256 views

How to prove that $\gcd(f_n(1),f_n(2),f_n(3),…)=1$ , where $f_n=\frac{x^{n+1}+(a-1)x^{k+1}-a}{x-1}$?

I have polynomial of the form : $ f_n= x^n+x^{n-1}+\cdots+x^{k+1}+ax^k+ax^{k-1}+\cdots+a$ where $\gcd(n+1,k+1)=1$ , $ a\in \mathbb{Z^{+}}$ , $a$ is odd number , $a>1$, and $a_1\neq 1$ and I want ...
-1
votes
2answers
141 views

Proof of even like powers?

Can someone show me the proof that difference of like even powers of any two numbers is divisible by the sum of the bases?
0
votes
2answers
79 views

$\gcd(P(a),Q(a),R(a),S(a),T(a))=1$ for any particular value of $a$?

Let's define five binomials as : $P(a)=2a+1$ $Q(a)=3a+4$ $R(a)=4a+9$ $S(a)=5a+16$ $T(a)=6a+25$ How to prove that : $\gcd(P(a),Q(a),R(a),S(a),T(a))=1$ for any particular value of $a$ , $(a\in \mathbb{...
1
vote
2answers
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$ ...
6
votes
4answers
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 ...
2
votes
2answers
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 ...
2
votes
2answers
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 ...
3
votes
3answers
735 views

If $\gcd(m,n)=1$ then $\gcd(2m-n-1,m-1)=2$?

How to prove following statement: If $\gcd(m,n)=1$, then $\gcd(2m-n-1,m-1)=2$, where $m,n$ are odd numbers and $m>n$. Since $m=2k_1+1$ and $n=2k_2+1$ we may write: $2m-n-1=2(2k_1+1)-2k_2-1-1=...
4
votes
4answers
195 views

Proof: If $n=ab$ then $2^a-1 \mid 2^n-1$

I don't know how to explain or how to prove the following statement If $n=ab$ and $a,b \in \mathbb{N}$ then $2^a-1 \mid 2^n-1$. Any ideas? Perhaps an induction? Thanks in advance.
1
vote
2answers
696 views

Use congruences to show that $6$ divides $n^3 – n$ for every integer $n$ [closed]

Use congruences to show that $6$ divides $n^3 – n$ for every integer $n$. I did this same problem using induction, and I don't understand how to do it using congruences. Is this using modulo?
1
vote
1answer
100 views

If $\gcd(a+1,b+1)=1 \Rightarrow \gcd(P(x),Q(x))=1$?

Let us define : $P(x)=x^{a}+x^{a-1}+\cdots+1$ $Q(x)=x^{b}+x^{b-1}+\cdots+1$ , where $a>b$ and $a , b \in \mathbb{N}$ Is it true that: If $\gcd(a+1,b+1)=1 \Rightarrow \gcd(P(x),Q(x))=1$ ?
2
votes
1answer
99 views

Divisibility, many unknowns

As I was solving a math problem, I stumbled upon a question: What conditions must $a,b,c,d,e$ meet for $n$ to be a natural number? (Frankly speaking, I would like all but one of $a,b,c,d,e$ to be ...
3
votes
0answers
2k views

Show that $\gcd(2^m-1, 2^n-1) = 2^ {\gcd(m,n)} -1$ [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ $\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ I'm trying to figure this out: ...
5
votes
3answers
409 views

What is the lowest positive integer multiple of $7$ that is also a power of $2$ (if one exists)?

What is the lowest positive multiple of $7$ that is also a power of $2$ (if one exists)? Not a homework question, I am not in school, I am just wondering what the answer is.
18
votes
3answers
2k views

Why does $a^n - b^n$ never divide $a^n + b^n$?

I'm working through the problems in Niven's number theory book, and problem 46 in section 1.2 (page 19) has me stumped. Prove that there are no positive integers $a, b, n > 1$ such that $(a^n - ...
0
votes
1answer
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.
-1
votes
3answers
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$.
30
votes
5answers
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 ...
6
votes
2answers
1k views

Fibonacci and Lucas identity

By the trial and error method I have observed the following identity by taking some numerical values. Those are $F_m$|$L_n$ is valid only if one of the following holds. a) $m = 1$ or $m =2$ b) $m = ...
1
vote
6answers
3k views

Proof that $\mathbb{Z}$ has no zero divisors

Everyone knows the rules of zero divisors like $$\forall \alpha,\beta\in\mathbb{R}\;:\;\alpha\cdot\beta = 0\Rightarrow\alpha=0\vee \beta=0.$$ But how can I prove it for $\mathbb{Z}$? My first try was ...
1
vote
4answers
555 views

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? ...
3
votes
4answers
270 views

How to show $a^{2^n}+1 \mid a^{2^m}-1$?

I've been struggling with this all day today. I imagine it's not very hard, but my algebra skills are terrible. So, how can I show that if $m>n$ and $a$ is a positive integer, then $$a^{2^n}+1 \mid ...
10
votes
3answers
4k views

Divisibility rules and congruences

Sorry if the question is old but I wasn't able to figure out the answer yet. I know that there are a lot of divisibility rules, ie: sum of digits, alternate plus and minus digits, etc... but how can ...
4
votes
2answers
272 views

Binomial division

Looks very easy, but I can't make it: $s \geq 2$ and $w \geq 2$ are prime numbers. $k$ is a natural number and $k \leq \min \{s,w \}$ Show that $\binom{s+w}{k}-\binom{w}{k} - \binom{s}{k}$ can be ...
4
votes
5answers
382 views

finding remainder by dividing a sum

Suppose I am dividing 4^30-2^50 by 5. I do understand that 4^30 will get converted to ...
4
votes
12answers
5k views

Prove that $6|2n^3+3n^2+n$

My attempt at it: $\displaystyle 2n^3+3n^2+n= n(n+1)(2n+1) = 6\sum_nn^2$ This however reduces to proving the summation result by induction, which I am trying to avoid as it provides little insight.
6
votes
3answers
2k views

For integers $a$ and $b$, $ab=\text{lcm}(a,b)\cdot\text{hcf}(a,b)$

I was reading a text book and came across the following: Important Results (This comes immediately after LCM:) If 2 [integers] $a$ and $b$ are given, and their $LCM$ and $HCF$ are $L$ and $H$ ...
13
votes
7answers
5k views

Proof for divisibility by $7$

One very classic story about divisibility is something like this. A number is divisible by $2^n$ if the last $n$-digit of the number is divisible by $2^n$. A number is divisible by 3 (resp., by 9)...