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)

-2
votes
0answers
12 views
1
vote
1answer
22 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 ...
7
votes
3answers
524 views

Prove that $x$ and $x+1$ are coprime numbers

Given $\{x \mid x > 1\}$, how do I prove that any given $x$ and $x+1$ are coprime?
0
votes
0answers
28 views

No prime number divides one

I was reading Euclid's theorem and came accross this affirmation but no prime number divides 1 Is there any mathematical proof or is it an axiom of number theory ? Can this affirmation be ...
1
vote
1answer
27 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.
-1
votes
3answers
98 views

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

What is an intuitive way to think about odd and even numbers? And about divisibility also...
4
votes
4answers
80 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
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
11 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 ...
1
vote
1answer
18 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
32 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 ...
3
votes
6answers
72 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 ...
7
votes
1answer
83 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 ...
1
vote
1answer
53 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
38 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?
4
votes
1answer
85 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?
0
votes
0answers
36 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 ...
0
votes
0answers
21 views
2
votes
2answers
41 views

Show $\gcd (a,b)=\gcd (b,r)$ if $a = bq + r$

Let $a, b$ be two integers with $b \neq 0$, and $q, r$ non-negative integers such that $a = bq + r$. How can we show that $\gcd (a,b)=\gcd (b,r)$?
4
votes
6answers
194 views

Proof that $a^5 b - b^5 a$ is divisible by $30$ for any integers $a$ and $b$

I am trying to prove that $a^5\times b - b^5\times a$ is divisible by $3$. The actual task is to prove divisibility by $30$ but I have managed to prove that the expression is divisible by $5$ and $2$. ...
0
votes
2answers
29 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
3answers
48 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
68 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 ...
2
votes
1answer
38 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 ...
4
votes
1answer
85 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 ...
-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 ...
1
vote
4answers
114 views

Find the value of $n$ such that $(n-6)$ is divisible by $6$, $(n-7)$ is divisible by $7$ and $(n-8)$ is divisible by $8$.

If $(n-6)$ is divisible by $6$, $(n-7)$ is divisible by $7$ and $(n-8)$ is divisible by $8$, then what is the value of $n $?
0
votes
2answers
32 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
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
54 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
192 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
57 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
58 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
103 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
13 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
23 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
141 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
24 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
32 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
695 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
28 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
79 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 ...