This tag is for basic questions about divisibility.
18
votes
5answers
1k views
Why $a^n - b^n$ is divisible by $a-b$?
I did some mathematical induction problems on divisibility
$9^n$ $-$ $2^n$ is divisible by 7.
$4^n$ $-$ $1$ is divisible by 3.
$9^n$ $-$ $4^n$ is divisible by 5.
Can these be generalized as
$a^n$ ...
16
votes
5answers
4k views
If $a^2$ divides $b^2$, then $a$ divides $b$
Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$.
Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
12
votes
5answers
2k views
Proof of the divisibility rule of 17.
Rule: Subtract 5 times the last digit from the rest of the number, if the
result is divisible by 17 then the number is also divisible by 17.
How does this rule work? Please give the proof.
...
12
votes
2answers
480 views
Proving there are an infinite number of pairs of positive integers $(m,n)$ such that $\frac{m+1}{n}+\frac{n+1}{m}$ is a positive integer
The question is:
Show that there are an infinite number of pairs $(m,n): m, n \in \mathbb{Z}^{+}$, such that: $$\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{Z}^{+}$$
I started off approaching this ...
12
votes
2answers
212 views
Prove $6 \nmid [\left( \sqrt[3]{28} - 3 \right)^{-n}]$
Prove that: $$6 \not\left|\ \left\lfloor\frac 1 {(\sqrt[3]{28} - 3)^{n}}\right\rfloor \ (n \in Z^+)\right.$$
($\lfloor x\rfloor$ = largest integer not exceeding $x$)
I am very bad as English and ...
11
votes
2answers
249 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 ...
9
votes
1answer
159 views
Elementary Number Theory; prove existence
Prove that there exists a positive integer $n$ such that
$$2^{2012}\;|\;n^n+2011.$$
I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ ...
8
votes
5answers
196 views
How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$
If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can´t find a way to use any of the elemental divisibility and gcd theorems to find them.
8
votes
3answers
142 views
Does $a^n \mid b^n$ imply $a\mid b$?
Does $a^n \mid b^n$ imply $a\mid b$? I think it does but haven't been able to prove it.
I don't know much number theory so an elementary answer would be great.
8
votes
3answers
188 views
Proof of Wolstenholme's theorem.?
According to the theorem :
$$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{p-1} =\frac{r}{q}$$
And we have to prove that $r= 0 \pmod{p^2}$.
(Given $ p>3$, ...
7
votes
5answers
176 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 ...
7
votes
3answers
208 views
Number of integers not divisible by $p$ and $q$
Here's a part of question from Siklos' "Advanced Problems in Core Mathematics":
How many integers greater than or equal to zero and less than 1000 are not divisible by 2 or 5? What is the average ...
7
votes
1answer
366 views
If $\gcd(a,b)=d$, then $\gcd(ac,bc)=cd$?
$A$ an integral domain, $a,b,c\in A$. If $d$ is a greatest common divisor of $a$ and $b$, is it true that $cd$ is a greatest common divisor of $ca$ and $cb$? I know it is true if $A$ is a UFD, but ...
7
votes
0answers
225 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 ...
6
votes
6answers
1k views
Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.
Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
6
votes
4answers
1k views
Simple divisibility proof
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.
6
votes
2answers
835 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?
6
votes
6answers
652 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 ...
6
votes
3answers
345 views
The positive integer solutions for $2^a+3^b=5^c$
What are the positive integer solutions to the equation
$$2^a + 3^b = 5^c$$
Of course $(1,\space 1, \space 1)$ is a solution.
6
votes
4answers
62 views
$20^{15} + 16^{18}$ is divided by 17
What is the reminder, when $20^{15} + 16^{18}$ is divided by 17.
I'm asking the similar question because I have little confusions in MOD.
If you use mod then please elaborate that for beginner.
...
6
votes
2answers
127 views
Smallest value of $(a+b)$
What can be the smallest value of $(a+b)$ , $a>0$ and $b>0$ where $(a+13b)$ is divisible by $11$ and $(a+11b)$ is divisible by $13$
This is what I have done so far.
We have
1) $a+ 13b = ...
6
votes
3answers
316 views
Prove that every positive integer $n$ is a unique product of a square and a squarefree number
I am trying to prove that for every integer $n \ge 1$, there exists uniquely determined $a > 0$ and $b > 0$ such that $n = a^2 b$, where $b$ is squarefree.
I am trying to prove this using the ...
5
votes
5answers
2k views
Prove $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ if $\gcd(a,b) = 1$
I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$
$\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ holds.
I think the first step should look something like this:
$d = \gcd(a+b, a-b) = \gcd(2a, a-b)$
...
5
votes
3answers
348 views
If $R$ is a commutative ring with identity, and $a, b$ are its elements that are divisible by each other, is it true that they must be associates?
Thank you very much!
My problem is:
If $R$ is a commutative ring with identity, and $a, b$ are its elements that are divisible by each other, is it true that they must be associates?
Here, $a$ ...
5
votes
3answers
110 views
Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]
The problem is following, prove that:
$$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$
I've tried solving this problem using mathematical induction, but I ...
5
votes
2answers
129 views
How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?
How to prove $\forall m,n\in\mathbb N$:
$$ 56786730 \mid mn(m^{60}-n^{60})?$$
Thanks in advance.
5
votes
3answers
262 views
Why (directly!) does every number divide 9, 99, 999, … or 10, 100, 1000, …, or their product?
A curiosity that's been bugging me. More precisely:
Given any integers $b\geq 1$ and $n\geq 2$, there exist integers $0\leq k, l\leq b-1$ such that $b$ divides $n^l(n^k - 1)$ exactly.
The ...
5
votes
3answers
554 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 ...
5
votes
2answers
219 views
Divisibility - Math Olympiad
Show that for any positive integer $m$, there is an infinite number of pairs of integers $(x,y)$ satisfying the conditions:
i) $\gcd(x,y)=1 $;
ii) $y \mid x^2+m$;
iii) $x \mid y^2+m$.
5
votes
2answers
290 views
Is Gauss's lemma valid for polynomials with coefficients in a GCD domain?
Wikipedia's proof of Gauss's lemma requires this theorem:
If $(C \mid S\cdot T) \land \lnot \operatorname{invertible}(C)$, $C$ has a non-invertible divisor in common with at least one of $S$ and ...
5
votes
2answers
785 views
Divisibility Rules for Bases other than $10$
I still remember the feeling, when I learned that a number is divisible by $3$, if the digit sum is divisible by $3$. The general way to get these rules for the regular decimal system is ...
5
votes
4answers
83 views
Prove or disprove the following statements involving greatest common divisor
Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
5
votes
4answers
309 views
If $n = m^3 - m$ for some integer $m$, then $n$ is a multiple of $6$
I am trying to teach myself mathematics (I have no access to a teacher), but I am not getting very far. I am just working through the exercises at the end of the book's chapter, but unfortunately ...
5
votes
1answer
28 views
Kernel of the evaluation map on a power series ring
Let $R$ be a commutative ring with unity and $r \in R$ a nilpotent element. Is it true that if $f \in R[[\epsilon]]$ satisfies $f(r) = 0$, then $(\epsilon - r) | f$ in $R[[\epsilon]]$? I tried solving ...
5
votes
1answer
52 views
Does this have a name: If an odd prime $p$ does not divide $a$, then $p$ divides $a^n + 1$ or $a^n - 1$
After seeing and doing a bunch of proofs like "For all $a$ in the natural numbers, then if $7$ does not divide $a$, then $7$ divides $a^3+1$ or $a^3-1$," I conjectured the following, but got stuck in ...
5
votes
1answer
245 views
Smallest number with a given number of factors
From my rather rudimentary explorations of this fascinating problem, I believe it to be a layered and rewarding subject for investigation.
My question, essentially, is: How do you find the smallest ...
5
votes
0answers
86 views
What's the most efficient algorithm for Divisibility?
What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
4
votes
12answers
881 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.
4
votes
6answers
364 views
Prove that $(n-m) \mid (n^r - m^r)$
In respect to a larger proof I need to prove that $(n-m) \mid (n^r - m^r) $ (where $\mid$ means divides, i.e., $a \mid b$ means that $b$ modulus $a$ = $0$). I have played around with this for a while ...
4
votes
5answers
290 views
Prove 24 divides $u^3-u$ for all odd natural numbers $u$
At our college, a professor told us to prove by a semi-formal demonstration (without complete induction):
For every odd natural: $24\mid(u^3-u)$
He said that that example was taken from a high ...
4
votes
3answers
286 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.
4
votes
3answers
206 views
Prove that $b\mid a \implies (n^b-1)\mid (n^a-1)$
Given natural numbers $a,b,n$, prove $b\mid a \implies (n^b-1)\mid (n^a-1)$.
I tried the simple method of beginning with $b\mid a \implies$ there exists a natural $k$ such that $bk=a$ and then ...
4
votes
3answers
118 views
Divide with remainder $\frac{x^2}{x^2 + x + 2}$
I am having a hard time long dividing:
$$\frac{x^2}{x^2 + x + 2}.$$
Could someone please show a step by step way to divide this, as I can only get it down to : $1 + \frac{x^2}{x + 2}$.
Thank you ...
4
votes
2answers
191 views
How to generate two numbers such that the smaller divides the larger
I am creating a children's math game and need an algorithm (that I can write in JavaScript) to generate two numbers such that the smaller always divides the larger. How can I do that?
4
votes
2answers
291 views
Proving divisibility
Let $x,y$ and $m$ be integers. Prove if $m | 4x$ + y and $m | 7x+2y$ then $m|x$ and $m|y$
4
votes
4answers
157 views
If $b^2$ is the largest square divisor of $n$ and $a^2 \mid n$, then $a \mid b$.
I am trying to prove this:
$n$, $a$ and $b$ are positive integers. If $b^2$ is the largest square
divisor of $n$ and $a^2 \mid n$, then $a \mid b$.
I want to prove this by contradiction, and I ...
4
votes
6answers
97 views
Solve $91x\equiv 84\pmod{147}$
So, I posted a similar question to this, and I know that the equation is solvable because $\gcd(91,147) = 7$ and $7 \mid 84$.
Plugging into Wolfram Alpha, I found that the solution is a line $21n + ...
4
votes
4answers
361 views
divisibility for numbers like 13,17 and 19 - Compartmentalization method
For denominators like 13, 17 i often see my professor use a method to test whether a given number is divisible or not. The method is not the following :
Ex for 17 : subtract 5 times the last digit ...
4
votes
2answers
216 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
1answer
129 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 ...
