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
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
129 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
105 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
33 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 ...
2
votes
1answer
99 views

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

I have two questions about a prove that I have to do for my mathematic study. I'm now thinking about it the whole day, but can't find the prove. Let $a,b \in \mathbb Z_{>0}$. (a) Prove: ...
0
votes
1answer
30 views

Number theory,GCD, coprime integers

I am sorry for the bad title but I really can't think of a better one. So I was learning about the euclidean algorithm and I see a statement that is hard for me to understand. In the book that I was ...
1
vote
1answer
128 views

How to find the number of divisors that are perfect squares and divisible by a number

Suppose $ n = 2^{14} 3^{9} 5^{8} 7^{10} 11^{3} 13^{5} 37^{10} $ , find the number of positive divisors that are both perfect squares and divisible by $ 2^{2}3^{4}5^{2}11^{2}$. It is quite simple to ...
1
vote
0answers
44 views

If p is a prime what values of $ a\leq p^{n}$ have $\text{gcd}(a, p^{n}) >1$?

Hi guys need your help. Sorry but I don't understand how to use latex. So really sorry for the writing. The question is if p is prime what values of $ a\leq p^{n}$ have $\text{gcd}(a, p^{n}) >1$? ...