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

learn more… | top users | synonyms

7
votes
4answers
139 views

Prove that $8640$ divides $n^9 - 6n^7 + 9n^5 - 4n^3$.

I found this problem in a book, I can't solve it unfortunately. Prove that for all integer values $n$, $n^9 - 6n^7 + 9n^5 - 4n^3$ is divisible by $8640.$ So far I've noticed that $8460 = 6! \times ...
0
votes
2answers
64 views

Let $p \in \mathbb{Z}$ so that if for all $a,b \in \mathbb{Z}$ where $p \mid (ab)$ is true then $p \mid a$ or $p \mid b$. Does this makes $p$ a prime?

I know this is related with Euclid's Lemma (the difference is that the lemma starts by assuming that $p$ is a prime which we don't here). I got this question in an exam and couldn't prove the ...
0
votes
0answers
25 views

When $n\mid\sum_{k=1}^{n}\phi (k)$

Consider this function. $$f(n)=\sum_{k=1}^{n}\phi (k)$$ where $\phi (k)$ is the Euler's totient function. I'm wondering are there infinitely many $n$ such that $n\mid f(n)$? For $n\leq 4000$ only ...
0
votes
6answers
66 views

How can I prove that if $a^7 = b^7$ then $a=b$, with $ a,b \in \mathbb{Z} $

I've tried with divisibility, meaning that since $a$ divides $a^7$, then $a$ divides $b^7$ and in the same way b divides $a^7$, but I can't seem to go further than this. What properties of the ...
2
votes
1answer
51 views

Prove, that $13\mid 10a+b$, when $13\mid a+4b$. [closed]

Prove, that $13\mid 10a+b$, when $13\mid a+4b$. I have no idea where to start, all similiar problems I have solved yet involved two expressions that were given and this only has one. What am I ...
-1
votes
1answer
18 views

divisibility criterion for integer numbers using congruences

let be a positive integer written in the form $$ \sum_{n=0}^{k}a(n)10^{n} $$ my question is how can i deduce using mathematics if the number is divisible by 2 , 4 or another higher integer using ...
0
votes
1answer
52 views

If $c = \gcd(a, b)$ then $c^2\mid ab$

I was given this question below in class today but I'm unsure on how to do it and where to start. We learnt about this in class today but it was with numbers rather than letters so it has thrown me ...
6
votes
2answers
94 views

$\gcd (ca, cb) = \gcd (a, b)c$ if $c > 0$ [duplicate]

Let $\gcd (a, b) = d$. So, $ax + by = d$ for some $x, y$. Then $(ca)x + (cb)y = cd$. Thus, $\gcd (ca, cb) = cd = \gcd(a, b)c$. Does it work?
5
votes
3answers
61 views

How to prove $\gcd(dm,dn)=d\cdot\gcd(m,n)$ [duplicate]

I want to prove the following equation : $$ (dm,dn) = d\cdot(m,n) $$ where $$ (m,n) = \gcd(m,n) \\ (dm,dn) = \gcd(dm,dn) $$ I tried this : $$ (dm,dn) \rightarrow \exists g_1 \in Z : g_1|dm, g_1|dn ...
2
votes
0answers
66 views

The Number of The 0's in a Factorial

I need to find that the number of the 0's at the end of the number is odd or even in a factorial. For example: $0! = 1$ (Even) $5! = 120 $ (Odd) $18! = 6402373705728000 $ (Odd) Dou you have any ...
43
votes
3answers
2k views

How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? [duplicate]

Possible Duplicate: Highest power of a prime $p$ dividing $N!$ How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
9
votes
2answers
3k 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, ...
0
votes
1answer
49 views

Understanding “divides” notation (aka “|”) in “d | (k,n)”

I'm wondering what the notation under the sigma symbol means: I understand that d | k means that d divides k. However, I am unsure of what d | (k,n) means. Does this mean d divides both k and n? Or ...
1
vote
1answer
25 views

Dividing with imaginary numbers, simplifying

Alright, so I have $8-\frac{6i}{3i}$. I multiplied by the conjugate of $3i$, and got $-18-\frac{24i}{9}$. This is the part that confuses me, because I don't know how to divide this. Can I divide ...
1
vote
1answer
30 views

If $\sigma _{1}(n)\mid \sigma _{2}(n)$, does $n$ has to be a perfect square?

Let's say $\sigma _{1}(n)\mid \sigma _{2}(n)$. Can we say, therefore $n$ has to be a perfect square? How to show that?
5
votes
1answer
40 views

Intended solution to proving $1994\mid 10^{900}-2^{1000}$ other than $1994\mid 10^{9k}-2^{10k}$

Earlier in the week, while tutoring in the math lab, a student came to me asking for assistance on proving the following statement: $$1994\mid 10^{900}-2^{1000}$$ The numbers were much too large ...
0
votes
1answer
35 views

If $m_1=m_2z$ and $n_1=n_2z$ where $z=\operatorname{lcm} (m_1,n_1)$, then $\operatorname{lcm}(m_2,n_2)=1$

I know if $z=\operatorname{lcm}(m_1,n_1)$, then (1) $n_1|z$ and $m_1|z$ (2) for every integer $k$, if $n_1|k$ and $m_1|k$, then $z|k$ and I know that $m_2|m_1$ and $n_2|n_1$ but I dont know what ...
7
votes
4answers
202 views

What is the sum of all the natural numbers between $500$ and $1000$.

What is the sum of all the natural numbers between $500$ and $1000$ (extremes included) that are multiples of $2$ but not of $7$?
0
votes
0answers
18 views

Divide value by range

Do you know a method to check if a value can be divided by a combination of integer value in a range? For example let's say I have 100, and I want to divide it by a cobination of value between 20 and ...
5
votes
1answer
70 views

Prime factorization and hcf [closed]

For any given integer $n$, we prime factorize it as follows $$n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_r^{k_r}. $$ Let $g = \gcd(k_1, k_2, \ldots, k_r)$ and $m_i = k_i / g$. The function $F$ is ...
11
votes
6answers
2k views

Show that any two consecutive odd integers are relatively prime

I've selected two integers $m=2k+1$ and $n=2k+3$ and I've tried to make a linear combination of the two such that it equals 1, but I'm sort of stuck and am not sure if this is a dead end or not. Any ...
0
votes
1answer
50 views

There exists an integer $m$ such that $1\vert m$, $2\vert m$, $3\vert m$, $4\vert m$,… $n\vert m$.

So, the exact question is, given that $n > 1$ is an integer, prove that there exists an integer $m$ such that $2\vert m$, $3\vert m$, $4\vert m$,... $n\vert m$. I am beyond lost on this, so any ...
6
votes
1answer
364 views

Showing $\gcd(2^m-1,2^n+1)=1$

A student of mine has been self-studying some elementary number theory. She came by my office today and asked if I had any hints on how to prove the statement If $m$ is odd then ...
6
votes
1answer
108 views

Proof that $\gcd(2^m-1,2^n+1)=1$ for odd $m$ using group theory

Below is a perfectly fine proof using basic tools of number theory: Showing $\gcd(2^m-1,2^n+1)=1$ Could we prove this more quickly using group theory? I would be very interested in seeing an ...
1
vote
1answer
82 views

Finding remainder when ${{45}^{17}}^{17}$ is divided by $204$

Find the remainder when ${{45}^{17}}^{17}$ is divided by $204$ This question came in an examination yesterday and I couldn't solve it. The answer that was given in the solutions booklet stated ...
25
votes
8answers
609 views

Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$

Prove that $$(n!)\cdot(m!)^n|(mn)!$$ I can prove it using Legendre's Formula, but I have to use the lemma that $$ ...
0
votes
4answers
62 views

Relatively Prime Integers

If $m$ and $n$ are relatively prime and $k\mid m$, show that $k$ and $n$ are also relatively prime. I haven't really any idea where to start with this. I have that if k|m then m=km' but I'm not ...
2
votes
4answers
88 views

How to prove $5^n − 1$ is divisible by 4, for each integer n ≥ 0 by mathematical induction?

Definition of Divisibility Let n and d be integers and d≠0 then d|n ⇔ $\exists$ an integer k such that n=dk" Source: Discrete Mathematics with Applications, Susanna S. Epp Prove the ...
0
votes
2answers
453 views

Counting 3-digit integers divisible by 6 but not by 9

How many $3$-digit counting numbers are exactly divisible by $6$ but not exactly divisible by $9$? I was able to find the answer for $6$ using the formula $T_n=a+(n-1)d$ but not sure how to find the ...
0
votes
1answer
19 views

$a =\prod_{i = 1}^{r} p_{i}^{ai}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$…

$a =\prod_{i = 1}^{r} p_{i}^{ai}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$, deduce a formula for the sum of the squares of the positive divisors of $a$. -The section we ...
0
votes
2answers
17 views

$a =\prod_{i = 1}^{r} p_{i}^{a_i}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$… [duplicate]

$a =\prod_{i = 1}^{r} p_{i}^{a_i}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$,Prove that $a$ is the square of an integer if and only if $a_i$ is even for each $i$. -The ...
3
votes
3answers
77 views

Show that we cannot have a prime triplet of the form $p$, $p + 2$, $p + 4$ for $p >3$

Show that we cannot have a prime triplet of the form $p$, $p + 2$, $p + 4$ for $p >3$ I was a bit lost with this proof until I found a similar looking proof-based question from a previous ...
1
vote
1answer
73 views

Prove or reject: if $a^2|b^3$ then $a|b$

I tried to find a counter example but failed!! If $a^2|b^3$ then it is obvious that $a|b^3$ because $b^3=ka^2=(ka)a=k'a$ but we hardly can say $a|b$
1
vote
1answer
104 views

Determine all $k$ such that $k^3+k+1$ is divisible by 11

The task is the following: Determine all $\ k\in\mathbb Z$ such that $k^3+k+1$ is divisible by 11 I assumed that "$k^3+k+1$ is divisible by 11" is saying $11|k^3+k+1$. That means I can rewrite it as ...
2
votes
1answer
18 views

How to work out the greatest lower divisor in a pair of divisors?

I don't know what it's called, so it's hard to explain, but say we have the number $12$, which can be $1 \times 12$, $2 \times 6$, or $3 \times 4$. I want the $[3, 4]$ pair because $3$ is the ...
3
votes
3answers
65 views

Compute a natural number $n\geq 2$ s.t. $p\mid n \Longrightarrow p^2\nmid n$ AND $p-1\mid n \Longleftrightarrow p\mid n$ for all prime divisor p of n.

Question: Compute a natural number $n\geq 2$ that satisfies: For each prime divisor $p$ of $n$, $p^2$ does not divide $n$. For each prime number $p$, $p-1$ divides $n$ if and only if $p$ divides ...
0
votes
1answer
39 views

If $\gcd(a,b)=D$, then why must there exists integers $x$ and $y$ such that $ax+by=D$? [closed]

If the greatest common divisor of two integers $a,b$ is $D$, then why must there exists two integers $x,y$ such that $ax+by=D$?
0
votes
1answer
85 views

Use the Euclidean Algorithm to show the $\gcd(56,72)|40$

Use the Euclidean Algorithm to show the $\gcd(56,72)|40$ How do I go about this since $b$ is larger than $a$? Usually it is the other way around when I use the Euclidean Algorithm to find the $\gcd$ ...
1
vote
2answers
48 views

Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3

Find the Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3. (Numbers are selected without replacement). I made a list like this: The sum of ...
8
votes
7answers
14k 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.
2
votes
1answer
63 views

Find all $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime

I'll try to format my question in a manner such that you can skip (irrelevant) parts. Exercise: Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime. Motivation: I'm trying to ...
4
votes
4answers
181 views

Remainder when ${45^{17}}^{17}$ is divided by 204

Find the remainder when ${45^{17^{17}}}$ is divided by 204 I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$. $204=2^2\cdot 3\cdot 17$
1
vote
1answer
52 views

If $m | (8n +7)$, $m | (6n + 5)$, prove that $m = ± 1$

If $m | (8n + 7)$, $m | (6n + 5)$,prove that $m = ± 1$ -We have just starting going over the "divides" notation, and I am aware of a few properties and theorems from my notes. I am; although, a bit ...
5
votes
3answers
103 views

The only positive integers that divide successive numbers of the form $n^2+3$ are $1$ and $13$

I stuck with this problem, I don't know how to start with. Prove that the only positive integers that can divide successive numbers of the form $n^2+3$ are 1 or 13.
15
votes
17answers
13k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
2
votes
2answers
25 views

Divisibility: $60 \mid (2x-y)(2y-z)(3z+2x)$, if $8x-10y+27z=0$

As the title says, given $x,y,z \in \mathbb{Z}$, where $8x-10y+27z=0$, prove that $(2x-y)(2y-z)(3z+2x)$ is divisible by $60$. I tried to bring the formula in a format of $(\cdots)(8x-10y+27z) + ...
1
vote
3answers
44 views

Proof of divisibility: $17 \mid 3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ [closed]

As the title says, prove that $3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ is divisible by $17$.
1
vote
2answers
67 views

Proof that $(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ [duplicate]

$(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ my work: I assumed $m = da$ , $n = db$ for $a,b \in \mathbb{Z}$. Now, $2^m - 1$ = $2^{da} - 1$ = $(2^d)^a - 1$ = $x^a - 1$ where $x = 2^d$. similarly ...
-1
votes
5answers
43 views

Divisibility by 101; a problem with induction [closed]

I was trying to show that $10^{2n}+(-1)^{n+1}$ is divisible by $101$. Would anyone help me with the induction step please?
13
votes
14answers
2k views

How to prove that $k^3+3k^2+2k$ is always divisible by $3$? [closed]

How can I prove that the following polynomial expression is divisible by 3 for all integers $k$? $$k^3 + 3k^2 + 2k$$