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
2answers
58 views

Solving a problem with a diophantine equation without trial and error.

I have the following problem: A teacher bought toys for the students of an academy, every toy for a boys costs $290$ and every toy for a girl costs $330$. If he spends $24300$, how many of each ...
0
votes
1answer
14 views

A question about divisibility

I'd like to check if what I did here is ok just in case. I'm asked to find the remainder of $a^2-3a+11$ knowing that the remainder of dividing $a$ by $18$ is $5$. What I did: The problem states ...
1
vote
2answers
71 views

Prove: $\text{if }a,b,c\in\mathbb{Z} \text{ and } a^2+b^2=c^2\text{ then }3\mid ab$

This is for a homework assignment. I am supposed to prove, $$\text{if }a,b,c\in\mathbb{Z} \text{ and } a^2+b^2=c^2\text{ then }3\mid ab$$ I've tried using direct proofs and proofs by contrapositive, ...
1
vote
3answers
77 views

Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$ Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$ Then $f(n+1) = (3^{n+1}+7^{n+1})-2$ $(3*3^{n}+7*7^{n})-2$ This is the part I get stuck. Any help ...
1
vote
2answers
28 views

How to prove divisibility of the difference between two numbers.

Recently I have come across a statement saying that if $x$ and $y$ are divisible by $a$, then $x - y$ is also divisible by $a$. How can I prove this? Does it also apply to sum of $x$ and $y$ ?
0
votes
3answers
23 views

Let $a$ be a positive integer. The sum of $a$ consecutive integers is divisible by $a$ if and only if $a$ is odd.

How would one prove this? Other than using cases to prove the if and only if part, how would I prove each case to complete the proof?
0
votes
3answers
109 views

How to prove if $n$ is prime and $n | a^2$ then $n | a$?

My professor assigned this for homework but I don't understand how to connect the dots. He suggested using the fact that $\gcd (x,y) \cdot \operatorname{lcm} (x,y) = xy$ but I'm not sure how that's ...
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
157 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
1answer
69 views

Prove something is divisible by a prime

Let $p$ be a prime. Prove that $\sum_{k=j}^{p-1} \frac{k!}{ j! (k-j)! }$ is divisible by $p$ $\forall$ $j \in \{0, ..., p-2\}$. Where this problem comes from: I am trying to prove that ...
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 ...
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 ....
2
votes
3answers
91 views

Divisor in $\mathbb{C}[X]$ $\implies$ divisor in $\mathbb{R}[X]$?

let $P \in \mathbb{R}[X]$ be a real polynomial divisible by a polynomial $Q \in \mathbb{R}[X]$ in $\mathbb{C}[X]$. How can I easily show that $P$ is also divisible by $Q$ in $\mathbb{R}[X]$? A simple ...
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
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 ...
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 ...
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 ...
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 ...
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
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
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
81 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 ...
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 ...
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
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 ...
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 ...
11
votes
1answer
217 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
97 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
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
65 views

The product of three consecutive natural numbers is divisible by $6$

Please give me feedback for my answer to this question. Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by $6$ My answer: True. Suppose $n$ is ...
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
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...
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 ...
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
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 ...
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 ...
3
votes
6answers
104 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
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
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 = ...
6
votes
3answers
82 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 ...