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
vote
2answers
33 views

If $\gcd(a,n)=1$ then there exist integers $x,y$ such that $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y \pmod n$

If $a$ is integer and $n$ is positive integer such that $\gcd(a,n)=1$ then there exist integers $x,y$ for which $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y\pmod n$. By Dirichlet's principle I ...
2
votes
2answers
68 views

Is a Number Divisible by 40

One of the "shortcuts" for determining if a number is divisible by 8 is to see if the last three digits are divisible by 8. One ...
4
votes
0answers
39 views

Extention of Euclid's GCD Algorithm. (The Art of Computer Programming, Volume 1, Edition 3, Section 1.2.1, Exercise 12)

Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$, needs the inputs to be positive integers. Exercise 12 provides an extension to this algorithm and allows $c$ ...
2
votes
3answers
57 views

Find all intergers such that $2n^2+1$ divides $n^3+9n-17$

Find all intergers such that $2n^2+1$ divides $n^3+9n-17$. Answer : $n=(2 \ and \ 5)$ I did it. As $2n^2+1$ divides $n^3+9n-17$, then $2n^2+1 \leq n^3+9n-17 \implies n \geq 2$ So $n =2$ is ...
-1
votes
1answer
40 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
924 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
88 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
105 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
94 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 ...