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
3answers
107 views

$\frac{2abc}{(a+b-c)(b+c-a)(c+a-b)}$ a positive integer

Find all triplets $(a,b,c)$ of positive integers so that $\gcd(a,b,c)=1$ and $$ \frac{2abc}{(a+b-c)(b+c-a)(c+a-b)} $$ is a positive integer. What I've done: first I looked with Mathematica for ...
0
votes
1answer
50 views

Easy way to divide $2^{1000}$ by $59$ [closed]

What will be the remainder when $2^{1000}$ is divided by $59$? What is the easiest way to calculate this?
1
vote
3answers
71 views

Is there a term that is divisible by $67$, in the sequence $10, 110, 1110, 11110, …$

Consider the sequence $10, 110, 1110, 11110, 111110, ...$ Here the $n$ the term $a_n=\sum \limits_{k=1}^n\left(10^k\right)$ Is there a term which is divisible by $67$ ? How can we show that?
5
votes
2answers
78 views

show that $2^k|n\Longleftrightarrow 2^k|a_{n}$

Let sequence $\{a_{n}\}$ such $a_{0}=0,a_{1}=1,a_{n}=2a_{n-1}+a_{n-2}$. show that $$2^k|n\Longleftrightarrow 2^k|a_{n}$$ I try to find the $\{a_{n}\}$ closed form ...
1
vote
1answer
40 views

Subsets and Divisibility

What is the size of the largest subset, S, of {1,2,...2013} such that no pair of distinct elements of S has a sum divisible by 3? So...I know the very basic divisibility by 3 rule that any number ...
2
votes
6answers
91 views

Prove that $n(n+1)(n+5)$ is a multiple of $6$

I need to prove that $n(n+1)(n+5)$ is divisible by 6. where $n$ is a natural number. I have used the method of induction. But not successful I got the expression $(k^3+6k^2+5k)+3k^2+15k+12$ when ...
2
votes
2answers
59 views

How do people come up with divisibility tests?

For example, the test for divisibility by $2$ is quite obvious. But I am quite intrigued by the others, particularly $3$, $7$ and $11$. Also I have come across tests for numbers as far as $50$. How do ...
0
votes
4answers
71 views

Prove that if a|bc then a|b or a|c for a, b, c positive integers where a is not zero [closed]

Prove or disprove (by providing a counter-example) that if a|bc then a|b or a|c for a, b, c positive integers where a is not zero.
1
vote
1answer
19 views

Find the remainder and quotient when we will divide $a$ by $q$

When we divide $a$ by $b$ we get remainder $r=10$ and quotient $q=7$ What will be the remainder and quotient when we will divide $a$ by $q$? My attempt: $$a=b\cdot ...
2
votes
1answer
53 views

How to prove that $(p^2)!$ is divisible by $(p!)^{p+1}$?

For each prime $p$, find the greatest natural power of $p!$, which divides the number $(p^2)!$ ($n!=1 \cdot 2 \cdot ...\cdot n$) My work so far: 1) $p=2 \Rightarrow p!=2; (p!)^2=4!=24 \vdots 8=2^3$. ...
0
votes
3answers
38 views

Which is more; even or odd positive factors?

Suppose $f(n)=$ $\{$ ( number of $n$'s positive even factors) $-$ (number of $n$'s positive odd factors) $\}$ How can we prove/disprove the below statement? $f(n)< 0 $ for half or more ...
2
votes
0answers
55 views

Prove or disprove $a^2\mid b^3\Longrightarrow a\mid b$

I need to prove or to give a counter-example: $$a^2\mid b^3\Longrightarrow a\mid b$$ My attempt: First, let's check with small integres,trying to find counter-example: $2^2\mid ...
2
votes
4answers
100 views

Prove or disprove $d\mid (a^2-1)\Longrightarrow d\mid (a^4-1)$

I need to prove or to give a counter-example: $$d\mid (a^2-1)\Longrightarrow d\mid (a^4-1)$$ My attempt: Yes, this is correct, First: $(a^2-1)=(a-1)(a+1)\\ (a^4-1)=(a-1)(a+1)(a^2+1)$ If ...
3
votes
2answers
89 views

Prove that $\gcd(a^2, b^2) = \gcd(a, b)^2$ [duplicate]

The problem's quite clear. Prove that $$\gcd(a^2, b^2) = \gcd(a, b)^2$$ This is easy to understand intuitively and using the Fundamental Theorem of Arithmetic would be easy but I want to prove it by ...
0
votes
2answers
71 views

Can a product of 4 consecutive natural numbers end in 116

So i was given this question with two parts: (a) Prove that the product of two consecutive even numbers is always divisible by 8. (b) Can a product of 4 consecutive natural numbers end in 116? For ...
0
votes
1answer
43 views

The primes $2s+1$ with the constraint that $s$ satisfy certain congruence relations and Euler's idoneal numbers.

I would like to prove the following statement: If $s>1$ is a positive integer and $s\equiv0$ modulo 3 and $s\equiv0$ modulo 4 and $2s+1$ is prime then $2s+1 = x^{2}+24y^{2}$ for some ...
0
votes
1answer
37 views

Reference request for a divisibility property of Fibonacci numbers

Define the Fibonacci numbers $F_n$ by $F_n=F_{n-1}+F_{n-2}$ and initial values $F_0=0$ and $F_1=1.$ I would like to get a reference for the following result: If $p$ is a prime number with $p \equiv ...
0
votes
1answer
25 views

Confused about a simplification step in induction

Hello - I don't know how they got from the 3rd line to the 4th line. I understand all other parts of the simplification.
0
votes
1answer
48 views

proof - GCD and Number Theory

I have been trying to solve these but have had no success. Please help by giving hints not answers. Assuming that $\gcd(a,b)=1$ prove the following: (a) $\gcd(a+b,a-b)=1$ or $2$. [Hint: Let ...
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
54 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
42 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
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 ...
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 ...
29
votes
0answers
683 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
232 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
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
503 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 ...