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)

0
votes
2answers
15 views

prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$

Prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$ I did this by contradiction: let $d=(k,m,n)$ so that $d\neq 1$; by definition of greatest common divisor $d|k, d|m, d|n$ ...
0
votes
1answer
57 views

When does $m$ divide $a^m$?

Let $a\ge 0$, $m\ge 1$ be integers. What can be said about $m|a^m$? I note that if $a=1$, then $m\not{|} a^m$ unless $m=1$ and if $a=0$, then always $m|a^m$. Are there any general results for the less ...
-12
votes
2answers
198 views

How is 2 a prime number if you can divide it evenly?

From what I know about prime numbers is that a number is considered a prime number when it's not evenly divisible, such as any number that has decimal points after you divide it. But I can't figure ...
3
votes
2answers
58 views

Counting divisibility from 1 to 1000

Of the integers $1, 2, 3, ..., 1000$, how many are not divisible by $3$, $5$, or $7$? The way I went about this was $$\text{floor}(1000/3) + \text{floor}(1000/5) + ...
-1
votes
7answers
59 views

If an integer a is such that a-2 is divisible by 3 then a^2-1 is divisible by 3. prove by direct method

How to prove that if a is number such that $a-2$ is divisible by $3$ then $a^2-1$ is divisible by $3$ using direct method. I know if $a = 2$ then $a-2 = 0$ is divisible by $3$ and $2^2-1 = 3$ is ...
3
votes
3answers
104 views

how to prove if $m^{2}|n^{2}$ then m|n just hint please. [duplicate]

How to prove the following?: Let $m,n\in \mathbb{N}$ ; $ \;m^{2}\mid n^{2}\Longrightarrow \;\;m\mid n$ Just a hint please. I tried two ways but did not work.
0
votes
1answer
15 views

prove that $(k,mn)=(k,m)(k,n)$ $\forall k\in \mathbb Z$ and $(m,n)=1$:

prove that $(k,mn)=(k,m)(k,n)$ $\forall k\in \mathbb Z$ and $(m,n)=1$: My attempt: let $b=(k,m)$, $c=(k,n)$ and $a=(k,mn)$then there exist $x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}\in \mathbb Z$ so that ...
5
votes
3answers
61 views

Do Question's Given GCD Statements Imply these New GCD Statements?

Are the following statements true or false, where $a$ and $b$ are positive integers and $p$ is prime? In each case, give a proof or a counterexample: (b) If $\gcd(a,p^2)=p$ and ...
1
vote
2answers
19 views

solve the equation in Z

Solve the equation over $\textbf{Z}$ : 2$x^2$ - 2$xy$ - 5$x$ - $y$ + 19 = 0 I tried to obtain some $(A+B)^2$ terms, but I didn't make it. Thanks for your time!
1
vote
1answer
30 views

solve this equation in Z

Solve the equation over $\textbf{Z}$ : $x^3$ - 3$y$ = 2 The only way I solve this problem was using the Fermat Theorem. Is there any chance to solve it without using the theorem? And the proof to ...
0
votes
2answers
25 views

Congruence and GCD relation proof

I came across this theorem: For all integers a,b,c and m>0, if d = GCD(c,m) then ...
0
votes
1answer
17 views

Find integers $k$ and $l$ such that $\gcd(-5775,-651)$ can be expressed in the form $ka + bl$

As the title suggests, I have to find the following: $k$ and $l$ such that $\gcd(-5775,-651)$ can be expressed in the form $ka + bl$ Now, the main issue, I have is figuring out how the negatives ...
1
vote
0answers
27 views

find all the divisors of $6$ and $4+2\sqrt{5}$,then find $\gcd(6,4+2\sqrt{5})$

By inspection we see that the divisors of $6$ are $1,2,3,6$ For $4+2\sqrt{5}$ we have $4+2\sqrt{5}=2(2+\sqrt{5})$ showing that $\gcd(6,4+2\sqrt{5})=2$ Is this method correct; if not, how can I do ...
3
votes
2answers
144 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 ...
2
votes
1answer
25 views

Solving a divisibility problem using group theory

Inspired by this I decided to show this: Let $P_n=\displaystyle\prod_{1\leq i<j\leq n} \big(x_i-x_j\big)$ where $x_1\,\dots\, x_n$ are arbitrary integers. Prove $n!\,\big|\, 2P_n$. I am ...
0
votes
1answer
40 views

What is the best way of solving for $x,y\in\mathbb N$ given the conditions $\begin{cases}x\mid y+a\\y\mid x + b\end{cases}$?

What is the best way of solving for $x,y\in\mathbb N$ given the conditions $\begin{cases}x\mid y+a\\y\mid x + b\end{cases}$? The letters $a,b\in\mathbb N$ denote constant known numbers. The ...
0
votes
2answers
29 views

Prove that if $d|a$, then $d||a|$

I have no idea where to take this. It says to consider both cases of $d|a$ and $d|-a$, but I don't how to prove that.
59
votes
13answers
12k 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 'quantity'. The totality ...
1
vote
5answers
33 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?
6
votes
1answer
697 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
1
vote
3answers
30 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
91 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
25 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.
5
votes
0answers
36 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 ...
0
votes
4answers
58 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 ...
3
votes
5answers
529 views

Is division of matrices possible?

Is it possible to divide a matrix by another? If yes, What will be the result of $\dfrac AB$ if $$ A = \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}, ...
0
votes
2answers
140 views

Long division: 24158 divided 6

Long division has always been a weakness of mine and some how I've gotten through school and sixth form without it, but i'd like to learn it, it's just that I have a problem with intuition. So I know ...
0
votes
2answers
27 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.
8
votes
5answers
293 views

Prove that $b\mid a \implies (n^b-1)\mid (n^a-1)$

Given natural numbers $a,b,n$, prove $b\mid a \implies (n^b-1)\mid (n^a-1)$. I tried the simple method of beginning with $b\mid a \implies \exists k \in \mathbb{N} $ such that $bk=a$ and then ...
5
votes
3answers
95 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
25 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 = ...
17
votes
3answers
664 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 ...
2
votes
0answers
42 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
22 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, ...
9
votes
1answer
549 views

Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?

There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example ...
2
votes
0answers
56 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. :)
0
votes
2answers
33 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
62 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
42 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
10 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
40 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 ...
1
vote
1answer
32 views

Help with proving bezout's theorem?

Let $a,b,c\in\mathbb Z$ where $d=\gcd(a,b)$ and $c$ is a multiple of $d$. Suppose that $(x=x_0, y=y_0)$ is one particular integer solution to $$ax+by=c.$$ Then the complete set of integer ...
1
vote
1answer
42 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$
2
votes
1answer
34 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 ...
0
votes
2answers
18 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 ...
8
votes
4answers
407 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 ...
0
votes
0answers
28 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
25 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!
3
votes
5answers
319 views

How to show that 7|(a^2+b^2) implies (7|a and 7|b)?

For my proof I distinguished the two possible cases which derive from 7|($a^2+b^2$): Case one: 7|$a^2$ and $7|b^2$ Case two (which (I think) is not possible): 7 does not divide $a^2$ and 7 does not ...
0
votes
2answers
38 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