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
3answers
50 views

How to get a number that is divisible by $n$ - without obviously seeing it?

There are lots of tricks where someone has to think of a number and you can 'guess' that number by just asking a couple of questions (see, for example, here). I'm looking for something kind of ...
1
vote
1answer
59 views

Solve a system of diophantine equations

I have a problem with elemental number theory. I started with the expression $$ (a - \frac{1}{b})(b - \frac{1}{c})(c - \frac{1}{a}) $$ and task to find all natural $a,b,c$ so that the result of the ...
11
votes
1answer
215 views

Curious number theory problem

$k,m,n\in\mathbb{N}$ satisfy $k^{m+n}=nm^n$. How can I show that $m=k$ and $n=k^k\,?$
3
votes
4answers
96 views

Show that $(x + 1)^{2n + 1} + x^{n + 2}$ can be divided by x^2 + x + 1 without remainder

I am in my pre-academic year. We recently studied the Remainder sentence (at least that's what I think it translates) which states that any polynomial can be written as P = Q*L + R I am unable to ...
0
votes
0answers
25 views

How to apply the generalised divisibility rule to numbers of the form $10^k+n$

This is kind of a long question but bear with me. There's actually a question mark at the end. I'm trying to apply the generalised (decimal) divisibility rules to numbers of the form $10^k+n$ where ...
1
vote
4answers
40 views

An exercise regarding polynomials

I guess it is a simple exercise though I'm not very good at polynomials. It asks: Find $m,n,p,q$ natural numbers such that the polynomial $X^m+X^n+X^p+X^q$ is divisible by $x^3+x^2+x+1$. Thank you in ...
1
vote
1answer
23 views

Find all positive integers n such that $n\mid\lfloor(n-1)!/(n+1)\rfloor$

Find all positive integers $n$ such that $n\ \big|\ \left\lfloor\frac{(n-1)!}{n+1}\right\rfloor$. The answer says that when $n<5$, the condition holds for $n=1$ only. But I think $n=2,3$ also ...
1
vote
1answer
35 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
-2
votes
3answers
132 views

An intutive way to think about odd and even numbers. [closed]

What is an intuitive way to think about odd and even numbers? And about divisibility also...
1
vote
1answer
20 views

Is my proof correct? Let $a, b, c\in\mathbb Z$. Prove that if $a\mid b$ and $b\mid c$, then $a\mid(b + c)$.

Let $a$, $b$, $c$ $\in\mathbb{Z}$. Prove that if $a\mid b$ and $b\mid c$, then $a\mid (b + c)$. My proof: since $a\mid b$, $b = k\cdot a$ for some integer $k$ since $b\mid c, c = l\cdot b$ for some ...
0
votes
1answer
145 views

Optimal strategy in Euclid's game

Euclid's game (also known as the Game of Euclid) is played as follows: the players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from ...
4
votes
4answers
89 views

Prove that $a^7-a$ is divisible by 168 when a is odd

so I saw a similar question that proves $168\mid(a^6-1)$ when $(42,a) = 1$. But for this problem I was not given that gcd$(a,42)=1$. When I factor out a I get $168\mid a\cdot(a^6 - 1)$ and since $a$ ...
1
vote
1answer
21 views

Greatest common divisor and exponent relationship

For a > 1 show that the gcd$(a^n - 1, a^m - 1) = a^{(m,n)} - 1$ What are some useful equalities that might help in proving this relationship? I believe the constrains for $m,n$ are all positive ...
1
vote
2answers
33 views

For any integer $a$, $\gcd(11a+5,2a+1)=1$.

How would I go by proving this statement? What I did was I tried using Proposition GCD Of One, so that $(11a+5)x + (2a+1)y = 1$, and $(11x+2y)a + (5x+y) = 1$. But I have no idea what to do from ...
8
votes
1answer
105 views

GCD of $a^n + b^n$ and $c^n + d^n$

Prove or disprove that there does not exists any integers $a,b,c,d > 1$ such that $a,b,c,d$ are pairwise coprime, and $a^n + b^n$ and $c^n + d^n$ are also coprime for all integer $n > 1$. I ...
3
votes
6answers
102 views

Proving $\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$

How would you go about proving that $$\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$$ for any two integers $a$ and $b$? Intuitively it is true because when you divide $a$ and $b$ by ...
1
vote
1answer
58 views

Coprimality of $2^n + 3^n$ and $5^n + 7^n$

Prove or disprove that for all positive integers $n$, $2^n +3^n$ and $5^n + 7^n$ are always coprime. This is not a homework problem, it is merely a problem I set myself after doing some number theory ...
1
vote
5answers
39 views

Let $n\ge 2$ be an integer. If $\gcd(a,b^n)=1$, then $\gcd(a,b)=1$

Then I know $ax+b^ny=1$, but I can't figure out what to do from here. What could I do to prove this?
0
votes
0answers
40 views

Consecutive natural numbers [duplicate]

Please I want to know what is the most appropriate expression that if it is asked to find the counterexample of "The product of any three consecutive natural numbers is divisible by 9" My expression ...
-1
votes
2answers
82 views

Given n, and m, find the smallest k such that - n divides lcm (m,k) ; m divides lcm (n,k) [closed]

ٍSo my question is cleared from the title. Any one has an idea to solve this problem ?? Thanks.
0
votes
2answers
71 views

Prove that ac=bd implies a=d and b=c (if a,b relatively prime and c,d relatively prime)

Suppose that $\mathbf{a}$ and $\mathbf{b}$ are relatively prime, and that $\mathbf{c}$ and $\mathbf{d}$ are relatively prime. Prove that $\mathbf{ac = bd}$ implies $\mathbf{a = d}$ and $\mathbf{b = ...
6
votes
3answers
81 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
-1
votes
3answers
65 views

If $2$ divides a number $a$, does $2^n$ divide $a$ ? $n$ is any integar

If $2$ divides a number $a$, does $2^n$ divide $a$ ? $n$ is any integer. This seems to be true for me, but I just want to make sure it applies for all numbers. example if a = 137 2 does not divide ...
4
votes
1answer
110 views

Primality of the number of obtained by concatenating the n consecutive digits

Let $f_n$ be the number obtained by concatenating the first $n$ numbers (in base 10). For example $f_1 = 1, f_3 = 123$ and $f_{13} = 12345678910111213.$ Now if $n$ is even or divisible by $5$ then ...
4
votes
1answer
238 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
2
votes
1answer
41 views

Show that $(x-a,x-b)=1$

Knowing that $K$ is a field, $a,b \in K$ different from each other,show that $x-a,x-b$ co-primes. We suppose that $\exists f(x) \in K(x)$ such that: $f(x)|x-a$ and $f(x)|x-b$ Then $\deg f(x) \leq ...
0
votes
2answers
33 views

How to prove that gcd(k! mod m, m) > 1, for every k > $\alpha$

I'm doing some exercises and I've read that, if $\alpha$ is the first prime factor of a number $m \geq 2$, then, for every $k \geq \alpha$, it is true that $gcd(k!\ mod\ m,\ m) > 1$. I can see ...
0
votes
1answer
75 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 ...
0
votes
1answer
18 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 ...
0
votes
2answers
18 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$ ...
3
votes
2answers
70 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
vote
1answer
31 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 ...
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!
0
votes
2answers
29 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
29 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 ...
2
votes
1answer
32 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
43 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.
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?
1
vote
3answers
37 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
137 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
32 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
68 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
157 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 ...
0
votes
2answers
33 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
155 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
37 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
712 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 ...
59
votes
12answers
13k 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 ...