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
5answers
36 views

if $gcd(a,b)=gcd(a,b,c)$ then I need to prove that $ax+by=c$ has solution in $\mathbb Z$

if $gcd(a,b)=gcd(a,b,c)$ then I need to prove that $ax+by=c$ has solution in $\mathbb Z$ that is: $gcd(a,b)|c$ but how can I prove it with the given hypothesis?
1
vote
3answers
43 views

How multiple of number is determined?

Problem 5 Project Euler 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. It is suggested in above example that, 2520 is divisible by ...
3
votes
1answer
152 views

Proof of $(ma+ nb, mn)=(a,n)(b,m)$

Let $a,b,m,n \in \mathbb Z$. If $(m,n)=1$ ( $m,n$ are coprime integers) prove that $(ma+ nb, mn)=(a,n)(b,m)$ I started the proof like this: Let $c,d,e$ be the greatest common divisors of ...
1
vote
1answer
34 views

Please help to prove the following.

a,b and c are integers and we know that a+b+c=(a-b)(b-c)(c-a) Prove, that a+b+c is divisible by 27. Thank you very much.
6
votes
0answers
171 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
1
vote
4answers
1k views

What is the remainder when 4 to the power 1000 is divided by 7

What is the remainder when $4^{1000}$ is divided by 7? In my book the problem is solved, but I am unable to understand the approach. Please help me understand - Solution - To find the ...
1
vote
2answers
53 views

GCD of two real numbers

How would I show that gcd($2a+1 , 9a+4)=1 $? Here $a$ is an integer. I used the definition of the greatest common divisor, but felt it is too lengthy.
5
votes
3answers
238 views

Prove $x^3-3x+4$ is irreducible in $\mathbb{Q}[x]$

I want to prove $x^3-3x+4$ is irreducible in $\mathbb{Q}[x]$. Eisenstein's criterion doesn't apply here, so I think the simplest method would be to use the Rational Roots Test, right? If I can use ...
1
vote
1answer
53 views

GCD for multivariable polynomial ring

I'm reading Lectures on Modules and Rings by T. Y. Lam. It's on page 32 of the book, example 2.19A. It reads: (2.19A) Example. Let $k$ be a field. Then in the commutative polynomial ring $R = ...
18
votes
3answers
786 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
60
votes
12answers
16k views

Dividing 100% by 3 without any left

In mathematics, as far as I know, you can't divide 100% by 3 without having 0,1...% left. Imagine an apple which was cloned two times, so the other 2 are completely equal in 'quality'. The totality ...
0
votes
4answers
2k views

Find the least value of x which when divided by 3 leaves remainder 1, …

A number when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6, gives a remainder of 4. Find the ...
2
votes
0answers
50 views

Proof relating to Euclidian Algorithm

The question is as follows: (1): Let m and n be positive integers with n < m and let r be the remainder when m is divided by n. Prove that $$r < \frac m2$$ (2): The Euclidean Algorithm for ...
0
votes
0answers
39 views

GCD and LCM Property

Let D = $\mathbb R + X\mathbb C[X]$ Show that $GCD(X, iX) = \mathbb R^\times$ and $LCM(X, iX) = \emptyset$ I have an outline of what to do but don't exactly know who to show all of it... First, ...
2
votes
0answers
66 views

$27^{2004} + 22^{2004} - 4^{2004} - 1$ is divisible by (options)

(A) $299$ (B) $296$ (C) $298$ (D) $297$ This kind of sums are too problematic. Please provide a method which could give the correct answer in about a minute. :)
1
vote
2answers
464 views

The least perfect square, which is divisible by each of 21,36 and 66 is (options)

(a) 213444 (b) 214344 (c) 214434 (d) 231444 Any short method to solve this question in 1 min?
2
votes
1answer
72 views

Relation between divisibility of polynomials in different rings, $h | f$ in $\mathbb{Z}[x], \mathbb{Z}/p^k\mathbb{Z}[x]$ and $\mathbb{F}_p[x]$

Let $p$ be a prime, $k$ a positive integer. Let $f,h \in \mathbb{Z}[x]$ be polynomials such that $h | f \mod p^k$ in $ (\mathbb{Z}/p^k\mathbb{Z})[x]$ $h \mod p$ is irreducible in $\mathbb{F}_p$ ...
0
votes
1answer
44 views

Is it true that gcd$(-n,0)=-n$ for all $n\in\mathbb{N}$?

We all know that gcd$(n,0)=n$ for all $n\in\mathbb{N}$. Then how about for negative numbers? Is it correct if I say gcd$(-n,0)=-n$ for all $n\in\mathbb{N}$ ? If $n=0$, then gcd$(0,0)=0$ which is ok. ...
0
votes
1answer
15 views

GCD property of Domain

Let D be a domain and $\emptyset \subset A \subseteq D^*$ If $x \in D^*$ and $GCD(xA)\neq \emptyset$ then $GCD(A)\neq\emptyset$ and $GCD(xA) = xGCD(A)$. I've already figured out how to show that ...
0
votes
1answer
53 views

GCD Domain Proof

Let $D = \mathbb{R} + X \mathbb{C}[X]$ Show that $\gcd_D(X^2,iX^2)=\emptyset $ Here is my plan so far... (and my questions) Suppose $f \in \gcd_D(X^2,iX^2) $. How do I show that because X is ...
3
votes
2answers
145 views

Find the number of series

Find the number of series $(a_1,..., a_{2n})$ that have terms from ${\{0,...9\}}$ so that: $$ 11|\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i $$ (this is not a homework) There is a similar problem ...
8
votes
4answers
483 views

Why does $ (\frac{1}{2})^∞ = 0?$

Recently while at my tutoring I had a question that said: "Aladin has a pair of magic scissors that can cut things in to tiny pieces. If he cuts a carpet in half, cuts the half into half and continues ...
1
vote
1answer
44 views

Show that $gcd(a,b) |d $ and hence $gcd(a, b) \leq d$, where $d$ is the smallest number of the form $ma+nb$

Show that if $d$ is the smallest element in the set $S = \{s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb \}$ such that $d = ax + by$ then $\gcd(a,b) |d $ and hence $\gcd(a, b) \leq d$
0
votes
2answers
20 views

Show that for any $s \in S$ where $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}$, we have $d|s$ where $d$ is the smallest element

Explain why the set $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb $} has a smallest element, call it d, so we know there exists $x,y \in \mathbb{Z}$ such that $d = ax + by$, and ...
0
votes
0answers
33 views

Prove that $s \not= \emptyset $ by showing that at least one of $|a|$ or $|b|$ is an element of $S$.

. I'm trying to show an alternative proof to Bezout's Lemma (let $a, b \in \mathbb{Z}$, then there exists $x,y \in \mathbb{Z}$ such that $gcd(a, b) = ax + by$). Heres one of the steps in proving it: ...
0
votes
0answers
27 views

Is this division proof correct?

Show that if a is an even integer then 2 divides a. Let a be 2k 2/2k By Division Algorithm 2k=2q so k=q I'm not sure if this is the correct way to go about it so any insight helps. Thanks!
2
votes
1answer
36 views

Biggest common divisor

Find the GCD of all the numbers from the set $$\{(n+2014)^{n+2014}+n^n\mid n\in \mathbb{N},n>2014^{2014}\}$$ Now I have the proof but i can't understand one thing Lets say $d$ is the GCD.Now let ...
3
votes
5answers
363 views

How to show that $7\mid a^2+b^2$ implies $7\mid a$ and $7\mid b$?

For my proof I distinguished the two possible cases which derive from $7 \mid a^2+b^2$: Case one: $7\mid a^2$ and $7 \mid b^2$ Case two (which (I think) is not possible): $7$ does not divide $a^2$ ...
0
votes
2answers
40 views

How to solve this problem [duplicate]

Find the number of numbers between $100$ to $400$ which are divisible by either $2,3,5,7$ Please give some shortcut or some easy way
1
vote
2answers
34 views

Show the equivalence: $ab|c \iff a|c$ and $b|c$

Let $a,b \in \mathbb{Z}$ \ {$0$} with $gcd(a, b) = 1$ and let $c \in \mathbb{Z}$. Show the equivalence: $ab|c \iff a|c$ and $b|c$ Also give an example of numbers $a,b \in \mathbb{Z}$ \ {$0$} and ...
0
votes
2answers
36 views

How would I prove for all a that a divides zero

I'm trying to prove for all a such that a divides zero. I can explain verbally why it works but I can't seem to be able to write it down in "proof" form. Could someone help me out?
3
votes
3answers
549 views

What are all positive divisors of 7 factorial?

I need to determine all the positive divisors of 7!. I got 360 as the total number of positive divisors for 7!. Can someone confirm, or give the real answer?
1
vote
2answers
50 views

Proof: Each common divisor c of a,b divides GCD(a,b)

there already exists a proof for this theorem: http://www.proofwiki.org/wiki/Common_Divisor_Divides_GCD This one, however, uses Bêzout's Identity. I'm not allowed to use this for the proof. So, I ...
0
votes
2answers
115 views

Show that if $\gcd(a,b)=1$ and $p$ is an odd prime, then [duplicate]

Show that if $\gcd(a,b)=1$ and $p$ is an odd prime, then ${\gcd(a+b,}\frac{a^p +b^p}{a+b}$$) = 1$ or $p$ Sorry about the duplicate In another answer, however, the sum $\sum\limits_{k=0}^{n-1} ...
0
votes
2answers
170 views

Bezout's Identity for polynomials

Im working out a problem where I find out the GCD of two polynomials using Euclid's Algorithm, and then I need to use Bezout's Identity to make $\gcd(r,s)=ra+sb$ The question gives me $x^5+1$ and ...
1
vote
2answers
57 views

Finding a gcd in the form of a monic polynomial

The question is to find the greatest common divisor (in the form of monic polynomial) in $\Bbb F_5[X]$ of $f=x^2-x+4$ and $g=x^3+2x^2+3x+2$ I used the Euclidian Algorithm for polynomials and found ...
1
vote
0answers
39 views

Congruence equations

Given positive integer $Z, N$ and a set of positive integer $S$. Find smallest $k \in \mathbb{Z^+}$ such that $$a*k +1 \equiv Z \pmod N \ a\text{ is a positive integer that we don't know, and}\\ i*k ...
1
vote
3answers
39 views

Greatest Common Divisor written proof

Here is what I am trying to prove: Let $a,b,c,d \in ℤ_+$ with gcd$(a,b)=1$. If $a|c$ and $b|c$, prove that $ab|c$. Does the result hold if gcd $(a,b)\neq 1$ ? I know that gcd $(a,b)=1$ can be ...
4
votes
4answers
38 views

greatest common divisor of two primes a,b

Here is the question I am trying to prove: If $a,b$ are relatively prime and a>b prove that $\gcd(a-b, a+b) \in \{1, 2\}$. Can I begin with something like $(a-b)k + (a+b)l = d$ where $k,l$ are ...
1
vote
0answers
52 views

$\left\lfloor(\sqrt[3]{28}-3)^{-n}\right\rfloor$ is not divisible by 6 [duplicate]

let $n$ be a positive integer. Prove that the following expression: $$\left\lfloor(\sqrt[3]{28}-3)^{-n}\right\rfloor$$ is not divisible by 6. $\lfloor x\rfloor$ is the greatest integer less than or ...
0
votes
2answers
169 views

Proof about pythagorean triples $(a,b,c)$: At least one of $a$ and $b$ is even.

How should I go about proving at least one of a and b is even when $$a^2+b^2 = c^2$$ This is similar to A conjecture about Pythagorean triples, but I do not understand the steps written in there. ...
1
vote
2answers
49 views

How do I prove divisibility by 3 without induction?

How do I prove that: $3$ divides $4^n-1$, where $n$ is a natural number, and $3$ divides $n^3-n$, where $n$ is a natural number? All without induction?(only number theory) Thanks !
0
votes
2answers
87 views

gcd multiplied by lcm

I've encountered a very confusing problem in my homework. Let a and b natural numbers. Then, let x = gcd(a,b) * lcm(a,b). The question asks what [number] is x below, in terms of a and b. I do not ...
0
votes
4answers
159 views

Show {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$}

I have the following problem: Let $a, b \in\mathbb{Z}$. Show that {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$} I understand that the Bezout's lemma says that $gcd(a,b) = ...
1
vote
1answer
40 views

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$.

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$. My Work: I considered the case where $n =-1$ , and the case $n \not= 1$. So when $n\not= -1$ we can let $n^2 - ...
2
votes
1answer
90 views

Proving divisibility by using induction: $133 \mid (11^{n+2} + 12^{2n+1})$ [duplicate]

If $n > 0$, then prove the following by using induction: $$133|(11^{n+2} + 12^{2n+1}).$$
1
vote
2answers
137 views

Find the next divisor without remainder

I divide a value and if the remainder is not 0 I want the closest possible divisor without remainder. Example: I have: $100 \% 48 = 4$ Now I am looking for the next value which divide 100 wihtout ...
1
vote
0answers
90 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
2
votes
1answer
73 views

Finding divisibility of a

Let $$a=\frac{72!}{(36!)^2}-1$$ Find whether $a$ is odd. $a$ is even. $a$ is divisible by 71. $a$ is divisible by 73. Multiple answers can be correct. I was able to find whether $a$ is even or ...
1
vote
3answers
42 views

Looking for the lowest number divisible by 1 to A.

What would the math equation be for finding the lowest number divisible by 1 to A? I know factorial can make numbers divisible by 1 to A but that dosn't give me the lowest number. Example of what I'm ...