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)

6
votes
1answer
60 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
80 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
111 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 ...
0
votes
4answers
33 views

Is there a quick parity test for integers expressed with odd radicies?

For integers expressed with an odd base, is there an easy way to tell if the number is odd or even? For an even base, if the ones digit is even, so is the integer. But this doesn't hold true for odd ...
6
votes
3answers
116 views

Prove that, $(2\cdot 4 \cdot 6 \cdot … \cdot 4000)-(1\cdot 3 \cdot 5 \cdot …\cdot 3999)$ is a multiple of $2001$

Prove that the difference between the product of the first 2000 even numbers and the first $2000$ odd numbers is a multiple of $2001$. Please show the method. I have started with the following ...
1
vote
1answer
25 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: ...
1
vote
1answer
31 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
37 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
34 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
74 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
192 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
39 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
34 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
62 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
130 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
279 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
117 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
908 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
78 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
23 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
23 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
64 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
3answers
95 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
49 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
93 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
47 views

GCD proof using fundamental theorem of arithmetic

prove: $\gcd(m,n)=1$ if and only if $\gcd(m^i,n^r)=1$ 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
71 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
69 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
25 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 ...
1
vote
1answer
29 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
42 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$ ...
3
votes
0answers
53 views

Multiple of $n$ and the sum of its digits is $k\geq n$.

Show that for every positive integers $k\geq n$, with $n$ not divisible by $3$, there is a positive integer divisible by $n$ and such that the sum of his digits is $k$.
2
votes
1answer
106 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. ...
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
61 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
28 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
21 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 ...
1
vote
3answers
39 views

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$ Should I prove this by induction? If so, how should I go about it?
0
votes
1answer
34 views

Understanding Bézout's identity's proof as given on wikipedea.

I am reading this proof of Bézout's identity. It starts as: For given nonzero integers $a$ and $b$ there is a nonzero integer $ax + by$, $x$ and $y$ are also integers. The minimum absolute value of ...
1
vote
0answers
28 views

On counting number pairs having a specific greatest common divisor.

I wanted to count natural numbers $k$ not exceeding the fixed $n \in \mathbb{N}$ and having a greatest common divisor $\gcd(n,k) = d$ naturally for some $d \mid n$. In more mathematical terms: $$ ...
2
votes
2answers
50 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
-1
votes
1answer
20 views

need help with equasion

Well. My computer has fritzed up and I'm having to perform some lenghy task, it's processing 20 files every 2 seconds, it's at 459000 of 854528 Roughly how long in seconds might it take? I've ...
-1
votes
2answers
28 views

GCD of polynomials in $\mathbb{F}_2[x]$

How can one show that $\gcd(x^4+x+1,x^4-x)=1$ in $\mathbb{F}_2[x]$? Is it because the polynomials do not share any irreducible monic polynomials i.e. $1, x, x+1$ as factors?
0
votes
1answer
50 views

gcd of polynomials over Z_7

I want the gcd of the two polynomials: $$f=x^5+3x^4+5x^3+x^2+x+3$$ $$g=2x^3+4x^2+x$$ in $Z_7[x]$. My approach: I use the euclidean algorithm and continue until I get no remainder. ...
5
votes
2answers
81 views

$a+b+c+d+e$ divides $a^5+b^5+c^5+d^5+e^5-5abcde$

Let $a,b,c,d,e$ be integers such that $a(b+c)+b(c+d)+c(d+e)+d(e+a)+e(a+b)=0$. Prove that $a+b+c+d+e$ divides $a^5+b^5+c^5+d^5+e^5-5abcde$. I'm reminded of the factorization ...
1
vote
1answer
30 views

GCD of polynomials by using Euclid's algorithm

Let $g = x^2 +6x -7$ and $f = x^4 - 1$. Find the GCD of $f$ and $g$. So I started by evaluating $f/g$ and the result is $q = x^2-6x+43, r = -300x+300$. I tried to follow the algorithm one step ...
0
votes
2answers
28 views

$c=\text{gcd}(a,b)$ means $\exists{x,y}\in{\mathbb{Z}}$ so that $a=cx$ and $b=cy$. Show $\text{gcd}(x,y)=1$

Obvious homework question, so hints please: Suppose $a,b \in{\mathbb{Z}_+}$ and $c=\text{gcd}(a,b)$. So we know $\exists{x,y}\in{\mathbb{Z}}$ so that $a=cx$ and $b=cy$. Show that ...
0
votes
3answers
52 views

Prove that $\gcd(ab,m)\mid\gcd(a,m)\gcd(b,m)$ [closed]

Prove that if $a,b,m\in\mathbb N\setminus\{0\}$, then $$\gcd(ab,m)\mid\gcd(a,m)\cdot\gcd(b,m)$$
2
votes
0answers
24 views

How do I know the cyclic subgroups of G generated by a are equal?

I had a question of understanding that I was hoping you guys could help me with. Suppose there exists a group in the integers. For the sake of my understanding, let's say the group is, G = $Z_{60}$. ...
1
vote
4answers
57 views

Prove that if $a$ divides $ b$ , and $a$ divides $b + 2$ then $a = 1$ or $ a = 2$.

For positive integers $a,b$, prove that if $a$ divides $b$ and $a$ divides $b + 2$ then $a = 1$ or $a = 2$. I know that if $a|b$ and $a|c$ then $a|b+c$ or $a|b-c$ but I can't figure out how to get ...