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

learn more… | top users | synonyms (1)

19
votes
5answers
3k 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$ ...
5
votes
2answers
509 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 ...
8
votes
1answer
620 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 ...
21
votes
5answers
9k 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 ...
3
votes
3answers
407 views

How to prove that $z\cdot\text{gcd}(a,b)=\text{gcd}(za,zb)$

I need to prove that $z \cdot \text{gcd}(a,b)=\text{gcd}(za,zb)$. I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you ...
6
votes
3answers
551 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 ...
1
vote
4answers
100 views

Prove that $(ma, mb) = |m|(a, b)$

I'm trying to prove that $(ma, mb) = $|$m$|$(a, b)$ , where $(ma, mb)$ is the greatest common divisor between $ma$ and $mb$. My thoughts: If $(ma, mb) = d$ , then $d$|$ma$ and $d$|$mb$ → $d$|$max ...
6
votes
5answers
3k 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)$ ...
12
votes
7answers
443 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.
1
vote
1answer
148 views

How to prove Greatest Common Divisor using Bézout's Lemma

The problem is to prove the following If $\gcd(a,b) = c$, then $\gcd(a^m, b^m) = c^m$ I know that this can be solved easily by proving that $c\mid a \implies c^m \mid a^m$ and $c\mid b \implies ...
1
vote
4answers
262 views

Divisibility and the Fibonacci sequence

While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it. Show that if the Fibonacci sequence has a term divisible by a natural number ...
14
votes
3answers
424 views

Prove $n\mid \phi(2^n-1)$

If $2^p-1$ is a prime,(thus $p$ is a prime,too) then $p\mid 2^p-2=\phi(2^p-1).$ But I find $n\mid \phi(2^n-1)$ is always hold, no matter what $n$ is.Such as $4\mid \phi(2^4-1)=8.$ If we denote ...
6
votes
1answer
91 views

$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1$, or $p$

Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$ Thanks in advance .
14
votes
7answers
654 views

$n^5-n$ is divisible by $10$?

I was trying to prove this, and I realized that this is essentially a statement that $n^5$ has the same last digit as $n$, and to prove this it is sufficient to calculate $n^5$ for $0-9$ and see that ...
0
votes
1answer
73 views

Divisibility of prime numbers

I have this exercise in my worksheet in the discrete mathematics course.I don't understand the part that deals with prime numbers in integer-divisibility. "Show that for a prime number $p$, if a ...
7
votes
3answers
1k 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 ...
8
votes
3answers
351 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$, ...
8
votes
5answers
301 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 \exists k \in \mathbb{N} $ such that $bk=a$ and then ...
8
votes
6answers
2k 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. ...
2
votes
4answers
173 views

Division of $q^n-1$ by $q^m-1$, in Wedderburn's theorem

I need this for a proof of Wedderburn's theorem: $$q^m - 1 | q^n - 1 \quad \Rightarrow \quad m|n$$ with $q>1 \in \mathbf{N}$ and $m,n \in \mathbf{N}$. I'd also like to know if it works the other ...
14
votes
2answers
746 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 ...
10
votes
4answers
293 views

Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

I can't crack this one. Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that $a,b,c,z \in \mathbb{Z}$).
0
votes
3answers
685 views

How to show that $\gcd(n! + 1, (n + 1)! + 1) \mid n$?

Let $n$ be a positive integer, $n!$ denotes the factorial of $n$. Let $d = \gcd(n! + 1, (n + 1)! + 1)$. Show that $d$ divides $n$. (Hint: notice that $(n+1)(n!+1) = (n+1)!+n+1$)
6
votes
3answers
793 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 ...
1
vote
5answers
207 views

$24\mid n(n^{2}-1)(3n+2)$ for all $n$ natural problems in the statement.

"Prove that for every $ n $ natural, $24\mid n(n^2-1)(3n+2)$" Resolution: $$24\mid n(n^2-1)(3n+2)$$if$$3\cdot8\mid n(n^2-1)(3n+2)$$since$$n(n^2-1)(3n+2)=(n-1)n(n+1)(3n+2)\Rightarrow3\mid ...
0
votes
5answers
187 views

Proving that if $\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;$ then $\;5\mid(a+b)$

Can you please help me a bit with this question? How do we show that $\;$ if $\;\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;\;$ then $\;5\mid(a+b)\;$? Thanks a lot!
13
votes
2answers
279 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
590 views

Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?

There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example ...
9
votes
3answers
282 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.
6
votes
3answers
399 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$ ...
3
votes
3answers
409 views

Number of divisors

How can I find number of divisors of N which are not divisible by K. ($2 \leq N$, $k \leq 10^{15})$ One of the most easiest approach which I have thought is to first calculate total number of ...
1
vote
2answers
3k 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 ...
8
votes
6answers
248 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 ...
6
votes
3answers
9k views

Find the largest prime factor

I just "solved" the third Project Euler problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? With this on Mathematica: ...
4
votes
5answers
145 views

If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$ [duplicate]

Prove or disprove 'If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$, with $a,b\not= 0$' I need to prove this statement. I think it is true and also the converse is true. I took some examples such as ...
4
votes
3answers
273 views

How does one attack a divisibility problem like $(a+b)^2 \mid (2a^3+6a^2b+1)$?

In my current line of investigation, I am running into [many] divisibility questions like the one in the title, i.e. $$ (a+b)^2 \mid (2a^3+6a^2b+1), \qquad(\star) $$ where $a > b \ge 1$ are ...
4
votes
3answers
874 views

If $2^n - 1$ is prime from some integer $n$, prove that n must also be prime.

I understand the idea of the proof. I just want to make sure I wrote my proof well. Suppose $n$ is not prime. Then $\exists x,y \in \mathbb{Z}$ such that $n = xy$. $2^{xy} - 1 = (2^x)^y - 1$ $ = ...
3
votes
2answers
2k 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 ...
2
votes
2answers
117 views

Asymptotic divisor function / primorials

Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial), and $\sigma(n)=\sum_{d|n}^{}d$ (divisor function). Could someone please tell me what the general asymptotic of $\dfrac{\sigma(p_n\#)}{p_n\#}$ is? It ...
2
votes
4answers
140 views

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$. I tried to set $\gcd(a, b)$ to $b$ and used the fundamental theorem of arithmetic to prove that it is divisible by $a$, but I ...
2
votes
3answers
86 views

System of two simple modular equations

$$x \equiv -7 \mod 13$$ $$x \equiv 39 \mod 15$$ I need to find the smallest x for which these equations can be solved. I've been always doing this using Chinese Reminder Theorem, but it seems that it ...
1
vote
4answers
105 views

How to solve the equation $n^2 \equiv 0 \pmod{584}$?

Well, I've confused when trying to solve this equation can anybody help me : $n^2 \equiv 0 \pmod{584}$ I tried to factorize the $584$ i got $584=2^3\times73$. so $n^2$ has to be divisible by $2^3$ ...
1
vote
2answers
87 views

Extended Euclidean Algorithm problem

I'm confused about how to do the extended algorithm. For example, here's the gcd part gcd(8000,7001) $$\begin{align}8000 &= 7001\cdot1 + 999\\ 7001&=999\cdot 7+8\\ 999&=8\cdot 124+7\\ ...
1
vote
4answers
160 views

$(a^{n},b^{n})=(a,b)^{n}$ and $[a^{n},b^{n}]=[a,b]^{n}$?

How to show that $$(a^{n},b^{n})=(a,b)^{n}$$ and $$[a^{n},b^{n}]=[a,b]^{n}$$ without using modular arithmetic? Seems to have very interesting applications.$$$$Try: $(a^{n},b^{n})=d\Longrightarrow ...
1
vote
4answers
2k views

Prove that if a, b, x, y are integers with ax + by = gcd(a, b) then gcd(x,y)= 1

How would I go about proving this: Prove that if a, b, x, y are integers with ax + by = gcd(a, b) then gcd(x,y)= 1
6
votes
3answers
120 views

Why if $n \mid m$, then $(a^n-1) \mid (a^m-1)$?

My Number Theory book says that for $n, m$ be positive integers and $a>1$, then $(a^n -1)\mid(a^m -1)$ if and only if $n\mid m$. I understand the proof for only if part, but in if part the ...
4
votes
1answer
239 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
4
votes
5answers
442 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
4answers
231 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
5answers
736 views

Is it possible to get 1/3 without dividing by 3?

So I need to divide a rectangle into 3 equals parts, but without fractions. It's one of those old "You have two jars of two sizes and need to get an exact amount of some other size" type problems, ...