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
54 views

Divisibility exercise

Now, I have an idea how to attempt this question with modulo arithmetic, but I was thinking if there was a solution that did not involve modular arithmetic. If $7 |(b^2+c^2)$ iff $7|b$ and $7|c$. I ...
1
vote
2answers
30 views

$3^a\mid s(n) \Rightarrow 3^a\mid n$

This is not a homework question, neither a championship problem (as far as I've searched in the net), and it came up noticing a singular pattern, involving the powers of $3$: "Prove or disprove that ...
3
votes
3answers
234 views

A polynomial with integer coefficient

I'm struggling with this question: Suppose $P(x)$ is a polynomial with integer coefficients such that non of the values $P(1),...,P(2010)$ is divisible by $2010$. Prove that $P(n)\neq 0$ for all ...
2
votes
3answers
30 views

Show that $x_0$ must be an integer. Conclude that $\sqrt[n]{2}$ is irrational for every $n \geq 2$

I have a problem in my workbook that is as follows: Let $f = x^n + a_{n-1}x^{n-1}+\dots+a_1x+a_0 = 0 $ with $a_i \in \mathbb{Z}$. Suppose there exists a rational number $x_0$ with $f(x_0) = 0$. ...
0
votes
2answers
161 views

Find the sum of all three-digit natural numbers that are not exactly divisible by 3.

Find the sum of all three-digit natural numbers that are not exactly divisible by 3, is the question. What quick ways are there of doing questions like these? Say it was, sum of all three digit ...
1
vote
5answers
90 views

prove that $3$ does not divide $n^2+1$

How do I prove that $3$ does not divide $n^2+1$, for all $n\in\mathbb{Z}$, thought of in separate cases, but did not get, induction also was unable to ....
0
votes
1answer
30 views

Number theory question maximum possible difference between $a$ and $b$

$1287a 45b$ is a 8-Digit number, where $a$ and $b$ are not zero. The number is divisible by 18. What is the maximum possible difference between $a$ and $b$? My solution: I first said since it's ...
3
votes
4answers
105 views

Prove $5 \mid 2^{n+1} + 3^{3n+1}$

I tried induction, so I assume the hypothesis and attempt to show $5 \mid 2^{n+2} +3^{3n + 4}$ but this doesn't help. I tried breaking it down into prime factorizations, but I do not see it.
2
votes
1answer
93 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
1
vote
1answer
87 views

Why does Euclid's algorithm taken one step past the GCD seem to yield the LCM?

In class we are going over Euclid's Algorithm. For example, we learned that for integers $m$, $n$:$$\gcd(m,n) = sm + tn$$ Where $s$ and $t$ are integers that can be plugged in to satisfy the ...
-1
votes
2answers
30 views

prove: (a|b*c) ^ (gcd(a,b)=1) implies a|c [duplicate]

i need help with the following prove: (a|bc) ^ (gcd(a,b)=1) implies a|c following these writing guidelines http://i.imgur.com/qpIYqPp.png What I know so far: By the Euclidean algorithm there are ...
2
votes
4answers
141 views

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$. I tried to set $\gcd(a, b)$ to $b$ and used the fundamental theorem of arithmetic to prove that it is divisible by $a$, but I ...
0
votes
1answer
34 views

proof with divisibility

this is the original question prove: $\forall c \in Z, a\neq 0 $and b both $ \in Z$ $a|b \iff c\cdot a|c\cdot b$ Then he corrected himself by saying for problem 1: to show that ca | cb implies a | b ...
0
votes
1answer
33 views

gcd and linear combinations proof

I'm trying to do extra book work to prepare for our final coming up but a lot of the book questions involve topics I'm unsure about. Prove: $n\in Z$, n=a multiple of gcd(a,b) $\iff$ n is a linear ...
20
votes
1answer
475 views

Is $\sum_{k=1}^{n} k^k / \sum_{k=1}^{n} k \in \mathbb{N}$ for some $n > 1$?

Let $ A = \sum_{k=1}^{n} k^k $ and $ B = \sum_{k=1}^{n} k$, where $n >1 $ is a positive integer. Is $A/B$ ever an integer?
0
votes
1answer
30 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
2answers
47 views

Let n be an integer greater than 3. Find a formula for gcd(n, n + 3)

Let $n$ be an integer greater than $3$. Find a formula for $\gcd(n, n + 3)$ for each of the cases : $1)$ $n \equiv 0\mod 3$ $2)$ $n \equiv 1\mod 3$ $3)$ $n \equiv 2\mod 3$ Any help would be greatly ...
0
votes
0answers
11 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
83 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
41 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
48 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
46 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
62 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
52 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 ...
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 ...
0
votes
0answers
26 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 ...
8
votes
3answers
691 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?
1
vote
1answer
37 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
135 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
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
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
167 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
23 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 ...
3
votes
6answers
105 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
107 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
61 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?
1
vote
2answers
51 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)$?
3
votes
6answers
211 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
87 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
74 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 = ...
2
votes
1answer
42 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
66 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
118 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
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
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$ ...
0
votes
1answer
76 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 ...