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

learn more… | top users | synonyms

4
votes
2answers
2k views

If $\gcd(a,b)=1$, then $\gcd(a+b,a^2 -ab+b^2)=1$ or $3$.

Hint: $a^2 -ab +b^2 = (a+b)^2 -3ab.$ I know we can say that there exists an $x,y$ such that $ax + by = 1$. So in this case, $(a+b)x + ((a+b)^2 -3ab)y =1.$ I thought setting $x = (a+b)$ and $y = ...
6
votes
4answers
3k views

Prove $\gcd(a+b,a^2+b^2)$ is $1$ or $2$ if $\gcd(a,b) = 1$

Assuming that $\gcd(a,b) = 1$, prove that $\gcd(a+b,a^2+b^2) = 1$ or $2$. I tried this problem and ended up with $$d\mid 2a^2,\quad d\mid 2b^2$$ where $d = \gcd(a+b,a^2+b^2)$, but then I am ...
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, ...
4
votes
3answers
924 views

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

I need to prove that $z\gcd(a,b)=\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 please give me ...
2
votes
2answers
3k views

Prove that if $a$ and $b$ are relatively prime, then $\gcd(a+b, a-b) = 1$ or $2$

Prove that if $a$ and $b$ are relatively prime, then $\gcd(a+b, a-b) = 1$ or $2$. I started off by putting $\gcd(a+b, a-b) = d$. This implies that there are two relatively prime integers $x_1, x_2$, ...
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. ...
-1
votes
1answer
231 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 ...
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
0answers
82 views

Given an array, how many no. of subsequnces of array such that gcd of numbers in that subsequence will be between a and b

A sub-sequence can be obtained from the original sequence by deleting $0$ or more integers from the original sequence. $L \le$ GCD(all numbers in subsequence) $\le R$ number of such sequences. For ...
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 ...
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 ...
7
votes
4answers
145 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
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 ...
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 ...
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
53 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
102 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
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 ...
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
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
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 ...
7
votes
4answers
231 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
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 ...
6
votes
1answer
382 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
109 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
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 ...
25
votes
8answers
638 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
93 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
502 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
80 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
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 ...
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$?