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
0answers
11 views

question about division algorithm described in handbook of applied crypto

http://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=9 gives the following as a division algorithm: So step 1 is making it so that $yb^{n-t}$ is the same length as x and then step 2 loops until the ...
0
votes
0answers
8 views

Showing that s'm is a common multiple of m and n

so in class teacher gave us this algorithm GCD(m,n)=GCD(n mod m, m). after that we used it to find s and t. for example we found GCD of 453 and 174 and their s and t by making a table like this ...
0
votes
2answers
43 views

If $\gcd(a, b) = 1$ then prove that $\gcd(a+b, a^2-ab+b^2) = 1$ or $3$?

If $\gcd(a, b) = 1$ then prove that $\gcd(a+b, a^2-ab+b^2) = 1$ or $3$? I am shamelessly asking how to solve the problem? I have no idea how to start and solve. Please help.
0
votes
3answers
23 views

Euclidean algorithm in the ring of polynomials over a field

I need some help with the following division proofs. I suppose my biggest problem is not being able to visualize the algebra for one GCD equaling another GCD. I'm not sure of how to arrange the ...
0
votes
2answers
38 views

Feedback on Euclidean Algorithm: $gcd(277, 301)$

Ans: $301 =277 \cdot 1 + 24$ $277 =24 \cdot 11 + 13$ $24 = 13 \cdot 1 + 11$ $13 = 11 \cdot 1 + 2$ $11 = 2 \cdot 5 + 1$ $2 = 1 \cdot 2 + 0$ Is this correct?
1
vote
1answer
38 views

Prove for all $ n \in N,gcd(2n+1,9n+4)=1$

Question: Prove for all $ n \in N,gcd(2n+1,9n+4)=1$ Attempt: I want to use Euclid's Algorithm because it seemed to be easier than what my book was doing which was manually finding the linear ...
1
vote
1answer
48 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 ...
1
vote
3answers
40 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 ...
10
votes
0answers
93 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?$
4
votes
1answer
99 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 ...
0
votes
0answers
18 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 ...
0
votes
4answers
34 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 ...
-2
votes
0answers
14 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
34 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
30 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
106 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...
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
12 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
73 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 ...
8
votes
1answer
90 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
114 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
38 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$. ...
-1
votes
2answers
34 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
52 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
69 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
39 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 ...
-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
55 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
196 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
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
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
14 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 ...