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)

-1
votes
1answer
37 views

Relations between the GCD of two numbers and the GCD of their linear combinations

(a) Prove that $a|b$ if and only if $\gcd(a,b) = a$. (b) Let $b > 9a$, Show that $\gcd(a,b) = \gcd(a,b−2a)$ (c) Show that If $a$ is even and $b$ is odd, then $\gcd(a,b) = \gcd(a/2,b)$ (d) Show ...
2
votes
1answer
24 views

Find sum of possible pairs for given LCM and GCD

I am given $A$ and $B$. I have to find out sum of $(m+n)$ for all pairs of numbers where $m\leq n$, $\gcd(m,n)=B$ and $\operatorname{lcm}(m,n)=A$ For $A=72$, $B=3$ Possible pairs will be - $(3,72)$, ...
0
votes
1answer
16 views

Find if there exist some combination of these digits that will be divisible by 8 or not

Let's say I am given some 100 digits and I have to find whether there can be any combination of these digits such that the number formed will be divisible by 8, how can I do that? I know divisibility ...
0
votes
1answer
16 views

Can this simple divisibility property on binomial coefficient be proved without Gauss' lemma?

Consider the following property : ( * ) if $n\geq 1$, then $a_n=\binom{2n}{n}$ is divisible by $2n-1$. One can show that ( * ) is true as follows : $2n-1$ divides $na_n$ (because of the identity ...
-2
votes
10answers
147 views

Show that the number $n$ is divisible by $7$ [duplicate]

How can I prove that $n = 8709120$ divisible by $7$? I have tried a couple methods, but I can't show that. Can somebody please help me?
1
vote
5answers
62 views

Find the greatest common divisor of $8^{10}+12$ and $8^5$ without a calculator.

Find the greatest common divisor of $8^{10} + 12$ and $8^5$ I found the answer using a rather silly method: I found the GCD of the two numbers by finding the GCD of all the three numbers ...
0
votes
2answers
28 views

Which number is divisible by $3^6$?

Which number is divisible by $3^6$? $30^2\times 75^4$ $15^2\times162$ $30 \times 18^2$ $6^2\times 30^3$ I cannot show any attempts that I have tried because I don't even know ...
0
votes
2answers
28 views

Proving divisibility of b and a

Let $a,b \in \mathbb{N}$ such that $2a=3b$. Show that $2|b$ and $3|a$. My Approach: My approach to this question is to find an expression for $b$ in a way that the expression is divisible by ...
3
votes
0answers
38 views

Trying to prove a congruence for Stirling numbers of the second kind

I am struggling with a demonstration for this: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace ...
10
votes
7answers
923 views

Prove by induction that an expression is divisible by 11

Prove, by induction that $2^{3n-1}+5\cdot3^n$ is divisible by $11$ for any even number $n\in\Bbb N$. I am rather confused by this question. This is my attempt so far: For $n = 2$ $2^5 ...
1
vote
2answers
38 views

Prove the relation on $\Bbb N \setminus \{0,1\}$ is a partial order

I'm a bit new to this material and trying understand some problem I'm solving Let $R$ be a relation on the set set = $ \{ N \setminus \{ 0,1\}\} $ that's defined like this: $aRb$ if there is an ...
1
vote
0answers
87 views

Counting arrays problem [closed]

Given N, M and D I need to count how many sequence of N elements a[1],a[2].....a[n] can be formed which satisfy these 2 conditions : Each element is between 1 ≤ Ai ≤ M. Greatest common divisor of ...
0
votes
2answers
47 views

What does the “or” symbol mean as in “$ d\mid a$”

What does the "or" symbol mean as in the following post: How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$? In particular, the symbol is used in the above linked post in the following ...
6
votes
1answer
58 views

Divisibility of numbers between $n^3$ and $n^3+n$

Let $n$ be a positive integer. Given are numbers $n^3,n^3+1,\ldots,n^3+n$. Of them, $a$ are colored red, and $b$ others blue. The sum of the red numbers divides the sum of the blue numbers. Prove that ...
-1
votes
3answers
78 views

Prove that if $2|(x^2-1)$, then $8|(x^2-1)$.

Prove that if $2\ |\ (x^2-1)$, then $8\ |\ (x^2-1)$.
0
votes
1answer
17 views

Show natural numbers ordered by divisibility is a distributive lattice.

I need a proof that the set of natural numbers with the the relationship of divisibility form a distributive lattice with gcd as AND and lcm as OR. I know it can be shown that a AND (b OR c) >= (a ...
1
vote
1answer
20 views

Division of complex numbers when to use what sign

I have two examples of dividing complex numbers, but both do the sign differently. The first is: $$\frac{a+bi}{c-di} \cdot \frac{c+di}{c-di}$$ the other is: ...
0
votes
1answer
28 views

Greatest Common Divisor Proof

Show that if $r_k = q_i r_{k+1} + r_{k+2}$, then $\gcd(r_k,r_{k+1}) = (r_{k+1},r_{k+2})$
1
vote
1answer
27 views

Polynomial greatest common divisor algorithem

I look for an algorithm for Polynomial greatest common divisor. I saw this at Wikipedia but I didn't understand where is the algorithm. If you have other source for this algorithm, or you can write ...
2
votes
0answers
30 views

divisibility and k-power sum

Let $a_{1},\dots,a_{n},\,n>2$ distinct natural numbers. Prove that if $p_{1},\dots,p_{r}$ are prime numbers and they divide $a_{1}+\dots+a_{n}$ then exists an integer $k>1$ and a prime $p\neq ...
2
votes
2answers
33 views

If $2a^2 = b^2$ then $2$ is a common divisor of $a$ and $b$?

The question is: Prove the statement or disprove it using a counterexample. If $2a^2 = b^2$, where $a,b\in \mathbb Z$, then $2$ is a common divisor of $a$ and $b$? The only thing that works ...
1
vote
2answers
44 views

Help with understanding this proof in discrete mathematics?

This is the question and solution: Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a − 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and ...
1
vote
0answers
163 views

Count arrays with GCD as D

Given N ,I need to count the number of array of integers which satisfy the following conditions : ...
1
vote
2answers
35 views

Possible to find integers $x,y$ such that $6x+15y=2$?

I know that in general, for two integers $a$ and $b$, there exist integers $x$ and $y$ such that \begin{equation} ax+by=gcd(a,b) \end{equation} In this case, let $a=6$ and $b=15$ and let the ...
1
vote
2answers
28 views

Prove $gcd(a,b)=gcd(a,2a+b)$

Call $gcd(a,b)=d$. Then $d|a$ and $d|b$. And if $c|a$ and $c|b$, then $c|d$. It's simple to show that $d$ is SOME divisor of $a$ and $2a+b$, since we already know $d|a$ and $d|b$, so it divides the ...
1
vote
1answer
60 views

For two natural numbers

For any two natural numbers $m$ and $n$, prove that $m^3+n^3+4$ cannot be a perfect cube.
1
vote
1answer
42 views

Find the GCD and LCM of the factorials of two given numbers

Find $\gcd(20!, 12!)$ and $\text{lcm}(20!, 12!)$. My answer is: $20=2^2 \times 5$ $12=2^2 \times 3$ GCD $= 2^2 = 4$ LCM $= 2^2 \times 3 \times 5 = 60$ .... But my teacher said that this symbol ...
8
votes
3answers
268 views

Prime numbers divide an element from a set

Show that if $p$ is a prime number different from 2 and 5, then it divides at least one of the elements of the set $\left \{ 1,11,111,1111,...\right \}$.
2
votes
1answer
102 views

Do these arithmetic rules work? They extend the number system by a zero not based on the empty set that is a divisor with unique quotients.

These rules are part of an attempt to define an additive identity in terms of division in basic standard arithmetic. The difficulties with defining division by $0$ are well known. In order to ...
6
votes
4answers
891 views

Prove that there is no number that divides both n and n+1

Statement There is no number $x > 1$ that divides both $n$ and $n+1$. Proof (my attempt) Indirect proof: \begin{align} x\mathbin{\vert} n & \implies n = xt_1 \\ x\mathbin{\vert}(n+1) ...
6
votes
1answer
61 views

Factorial division and remainders: 100!+102! mod 100

I'm having some issues with factorial division. I've been asked to determine the remainder of $11!$ under division by $12$. My logic was to state that $11! = 1\cdot2\cdot3\cdot4\cdots$ stopping there ...
0
votes
1answer
19 views

Lowest divisible number in number string

A number is arranged in a pattern like: 12345678910111213141516... What is the lowest value of that pattern divisible by 72? They are single numbers, not seperate (i.e. first in sequence is 1, ...
2
votes
0answers
22 views

To calculate what is $\sum_{1 \le m<n ;(m,n)=1} m^2$ or what is the remainder when $\sum_{1 \le m<n ;(m,n)=1} m^2$ is divided by $n$? [duplicate]

For an integer $n >1$ , what is the sum of the squares of all the positive integers that are less than $n$ and relatively prime to $n$ that is I am trying to calculate $f(n):=\sum_{1 \le m<n ...
2
votes
2answers
46 views

Prove if $3$ does not divide $n$, then $n^2=1+3k$ for some integer $k$

I am proving by cases but am getting confused. I am not sure if this leads to a contradiction or not. Here's what I have so far: Direct Proof. Suppose $3$ does not divide $n$. Case 1: remainder ...
5
votes
4answers
93 views

Prove that $13\vert(3^{n+1} +3^{n} +3^{n-1})$

Prove that $3^{n+1} +3^{n} +3^{n-1}$ is divisible by $13$ for all positive integral values of $n$
1
vote
2answers
45 views

Finding zeroes of $x^3-5x^2+11x+17$

I'm trying to find all the zeros of $x^3-5x^2+11x+17$. I figured the possible zeros as being +/- 1, +/- 17$. The book says that -1 is supposed to be a factor, but I tried dividing the polynomial by ...
3
votes
3answers
87 views

prove by induction that $29^n - 21^n$ is always divisible by $8$

I have to prove by induction that that $\forall n \in N,$ $8 | (29^n - 21^n) $ . I understand how to prove things with induction generally, but im not sure where to even start with this one. I ...
0
votes
2answers
23 views

GCD proof using fundamental theorem of arithmetic

I believe you need to do something with fundamental theorem of arithmetic to prove one of the sides. Not quite sure though. Help is appreciated.
1
vote
3answers
69 views

Are there in pure mathematics ensembles of number's which not divided by them self except $0$?

In pure mathematics we know well that each number divided by him self except $0$ , the question that let me confused is: Is there a proof in pure mathematics show to us that there are others ...
7
votes
1answer
66 views

If two elements a,b have a gcd, do then a*t,b*t also have a gcd?

Let $M$ be a commutative cancellative monoid. For elements $a,b \in M$ a gcd of $a,b$ is an element $\mathrm{gcd}(a,b)$ with the (universal) property $\forall c \in M (c |\mathrm{gcd}(a,b) ...
0
votes
1answer
19 views

Finding the number that gives remainder equal to 0

Hi i'm not english so I'll try to explain this as good as I can . If we have for example 250 : 5 = 50 , remainder 0 let's say I don't know the number i'm going to divide (because it is generated ...
-3
votes
2answers
40 views

How to show $a c\equiv bc\pmod{n}$ where $n \ge 2$ does not imply $a \equiv b \pmod n$? [closed]

How to show $a c\equiv bc\pmod{n}$ where $n \ge 2$ does not imply $a \equiv b \pmod n$? Would it be possible for someone to go over this step by step?
1
vote
1answer
25 views

Proving n is not divisble by m using Division Algorithm

When $n$ and $m$ are integers, how could I write a statement equivalent to the statement "$n$ is not divisible by $m$" using ideas from the Division Algorithm?
1
vote
4answers
38 views

If $(a,c)=1$ and $(b,c)=1$, prove $(ab,c)=1$.

I'm posed with the problem in the title, Let $a,b,c\in\mathbb{Z}$. Then if $(a,c)=1$ and $(b,c)=1$, prove $(ab,c)=1$. (By the way, $(a,c)=1$ means that the greatest common divisor of $a$ and $c$ ...
2
votes
1answer
49 views

Finding the number of divisible integers in the range $[1, 1000]$.

Sorry if this is a stupid question. I am asked to find the number of positive integers in the range $[1, 1000]$ that are divisible by $3$ and $11$ but not $9$. Here's how I $\text{tried}$ to do it. ...
0
votes
0answers
34 views

Round table and division of numbers, need proof.

Let's assume that k-number of people are sited on a round table (k>=2). Each of them chooses a card with a number from 1 to n where n>=k. Each card has a different number (2 people can't pick a card ...
1
vote
1answer
42 views

synthetic division with $i$ in divisor

I divided $x^3-4x^2+4x-16$ by $-2i$ using synthetic division and got a remainder of $-8i-8$. Is that right? I'm not sure I'm doing this right.
1
vote
2answers
42 views

Maximum GCD of two polynomials

Consider $f(n) = \gcd(1 + 3 n + 3 n^2, 1 + n^3)$ I don't know why but $f(n)$ appears to be periodic. Also $f(n)$ appears to attain a maximum value of $7$ when $n = 5 + 7*k $ for any $k \in \Bbb{Z}$. ...
0
votes
1answer
27 views

Solve denominator so quotient is whole number?

I have a simple equation. road_length = ROADLENGTH / ROADSPACING The problem is, I really need road_length to be a whole number because it's used in FOR loop in ...
0
votes
2answers
16 views

Prime Factorizations that divide each other

Let n have prime factorization n = p^s1 · p^s2 · · · p^sk and let m have prime factorization m = q^t1 · q^t2 · · · q^tl If n|m, what must be true about the corresponding lists of primes and the ...