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

learn more… | top users | synonyms

2
votes
1answer
43 views

Divisibility of Binomial Coefficients by a Composite Number [duplicate]

I am aware of proof of divisibility of binomial coefficients of a prime $p$. I've seen it is easy to show that when $0<k<p$ $$\binom{p}{k}\equiv 0 \mod p$$ Can there be anything stronger. ...
3
votes
1answer
52 views

When does $\phi (n) \mid n $?

I need to find all the integers such that $\phi (n) \mid n $, where $\phi$ is the totient function. Using $$\phi(n)=n\prod(1-1/p)$$where the product runs over all prime factors of n, one gets that ...
4
votes
1answer
41 views

a number n as pa+qb

How can we express a number $n$ as $pa+qb$ where $p \geq0$ and $q \geq 0$ and $p$ and $q$ can't be fraction. In contest I got a puzzle as if we can express $c$ as sum of $a$ and $b$ in form $pa+qb$. ...
5
votes
8answers
161 views

Prove that $6$ divides $n^3+11n$?

How can i show that $$6\mid (n^3+11n)$$ My thoughts: I show that $$2\mid (n^3+11n)$$ $$3\mid (n^3+11n)$$ And $$n^3+11n=n\cdot (n^2+11)$$ And if $n=x\cdot 3$ for all $x \in \mathbb{N}$ then: $$3\mid ...
7
votes
4answers
141 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 ...
4
votes
1answer
84 views

Probability that $7^m+7^n$ is divisible by $5$

If $m,n$ are chosen from the first hundred natural numbers with replacement, the probability that $7^m+7^n$ is divisible by $5$ is? $$7^m+7^n=7^m(1+7^{n-m}), n\ge m$$ The above expression is ...
0
votes
2answers
65 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
27 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 ...
27
votes
0answers
669 views

How to solve this two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I can not progress ...
0
votes
6answers
67 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 ...
5
votes
1answer
112 views

Finding Divisibility of Sequence of Numbers Generated Recursively

I have the following generating function: $$E(x)=\frac{2e^x}{e^{2x}+1+2x}=\sum_{n=0}^\infty {E_n}\frac{x^n}{n!}$$ which generates a sequence of integers below $$\{1, -1, 3, -15, 93, -725, 6815, ...
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
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 ...
5
votes
4answers
1k views

Factorial question: number of trailing zeroes in 125! [duplicate]

How many zeros are after the last nonzero digit of 125! ? The answer is 31, but how do you solve it?
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
31 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
69 views

Let's $1,2,3,\cdots,2005,2006,2007,2009,2012,2016,\cdots$ a sequence of integers defined by :

Let's $1,2,3,\cdots,2005,2006,2007,2009,2012,2016,\cdots$ a sequence of integers defined by : $ x_{k}=k$ if $1\leq k\leq 2006$ And $ x_{k+1}=x_{k}+x_{k-2005}$ if $k\geq 2006 $ Prove ...
0
votes
1answer
36 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 ...
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
3answers
62 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 ...
0
votes
1answer
51 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 ...
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 ...
-1
votes
1answer
230 views

Set of all $n$; $n={d^2_1 + d^2_2 + d^2_3 +d^2_4}$

$A$ is the set of all $n$ numbers where $n={d^2_1 + d^2_2 + d^2_3 +d^2_4}$. Here $1=d_1<d_2<d_3<d_4$ where $d_1,d_2,d_3,d_4$ are the $4$ smallest divisors of $n$. As an example ...
1
vote
1answer
83 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 ...
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
92 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
500 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
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 ...
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 ...
3
votes
3answers
79 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 ...
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 ...
1
vote
1answer
74 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
105 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
66 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 ...
7
votes
4answers
226 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
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$?
1
vote
2answers
54 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 ...
2
votes
1answer
65 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
187 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
53 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 ...
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$.
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) + ...
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$$
0
votes
1answer
31 views

Prove a relation is transitive

I've stumbled upon this question in my discrete math book: Prove $$ R = \{(x,y) \in N \times N \ | \ 2x \mid y^2 \} $$ is transitive. I tried thinking about it having to do something with division ...
0
votes
1answer
46 views

What is the simplest way to show that ${(p-1)! \over (k)!(p-k)!}$ is an integer?

In the proof of $p$ | $\binom{p}{k}$ (p divides $\binom{p}{k}$) where $p$ is prime, what is the simplest way to show that $${(p-1)! \over (k)!(p-k)!}$$ is an integer?
1
vote
2answers
62 views

Is this true :$\zeta(s-1)=\sum_{n=1}^{\infty}\frac{\gcd(n,n)}{{\operatorname{lcm}(n,n)}^{s}}$?

I would like to give other representation for zeta function using fundemental arithmitic I have got this: $\zeta(s-1)=\sum_{n=1}^{\infty}\frac{\gcd(n,n)}{{\operatorname{lcm}(n,n)}^{s}}$ where ...
0
votes
1answer
370 views

Number of positive integral divisors

I understand in order to find number of divisors, you need to follow following method, But I don't seem to find why it works. In order to find number of divisors a number has, you find the prime ...