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)

5
votes
3answers
825 views

Prove by induction: $2^n + 3^n -5^n$ is divisible by $3$

Let $P(n) = 2^n + 3^n - 5^n $. I want to prove that $P(n)$ is true for all integers $n\geq 1$. The basis step for this proof is easy enough: $P(1)$ is divisible by $3$. For the inductive step, I ...
0
votes
3answers
16 views

Factors of polynomial not passing the Bezout's identity test

When factoring $x^3 - 2x^2 - 4x - 8$ the result you get is $(x-2)(x^2 - 4)$ or $(x-2)^2 (x+2)$ , meaning that the mentioned polynomial is divisible by each of these factors. When using the Bezout's ...
1
vote
1answer
24 views

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.. I am totally lost; at first I thought this could be done by induction, but unfortunately this is not possible (at least I ...
23
votes
6answers
11k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
0
votes
1answer
47 views

If $a^2$ divides $b^3$, then $a$ divides $b$.

I want to prove or provide a counterexample to the following statement: $a^2|b^3 \Rightarrow a|b$. I know that $a^k|b^k \Rightarrow a|b$. My thought is that, e.g in the case of $k = 3$, where we ...
0
votes
1answer
33 views

Prove elements of a set are not uniquely representable.

Let $E = \{2k: k \in \Bbb{N}\}$, and let $M = \{m = (2r)(4a + 2) : r, a \in \Bbb{N}\}$. Prove that some elements in $E$ are not uniquely representable as products of elements of $M$, e.g. ...
-1
votes
0answers
16 views

How can I prove injectivity of this function

How can I prove that this function is injective: $f(x) = \dfrac{x(x+2014)}{\gcd(x, x+2014)}$ Domain and codomain: strictly positive natural numbers Where $\gcd$ is the greatest common divisor. I ...
1
vote
5answers
48 views

Let $n$ be a three digit number. Prove or give a counter example: $9|n$ if and only if the digits of $n$ sum to a multiple of $9$.

Let $n$ be a three digit number. Prove or give a counter example: $9|n$ if and only if the digits of $n$ sum to a multiple of $9$. I was able to go from left to right. But I'm having a hard time ...
1
vote
2answers
41 views

If $X$ and $Y$ are coprime to $Z$, then so is their product $XY$

Given is $X$ is coprime to $Z$ and $Y$ is coprime to $Z$ prove $XY$ is coprime to $Z$. I know you can use Bezout's lemma to say $1=aX+bZ$ and $1=cY+dZ$ but I don't know how to actually do the proof. ...
0
votes
2answers
48 views

If $\gcd (x,4) = 2$ and $\gcd(y,4) = 2$ then $\gcd(x+y,4) = 4$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $(x, 4) = 2$ and $(y, 4) =2$, then $(x + y, 4) = 4$, where $(a,b)$ denotes the ...
3
votes
3answers
11k views

Numbers till 400 divisible by 2, 3, 5, 7

I stumbled upon the following in a book: till 400 all even numbers will be divisible by 2 ( 200 even numbers) remaining 200 odd numbers 1 3 5 7 9 ..... 399 200/3 = 67 will be divisible by 3, ...
2
votes
4answers
70 views

Proving that $x^5 = x \pmod{10}$ for every integer $x$. [duplicate]

Show that $x^5 = x \pmod{10}$ for every integer $x$. How can I approach this? Should I use induction? I am stuck trying to get it in terms of $x+1$. Some feedback would be appreciated.
1
vote
7answers
83 views

Prove that $gcd(a, b) = gcd(b, a-b)$

I can understand the concept that $\gcd(a, b) = \gcd(b, r)$, where $a = bq + r$, which is grounded from the fact that $\gcd(a, b) = \gcd(b, a-b)$, but I have no intuition for the latter.
4
votes
1answer
57 views

Prove that there are no positive integers $a, b$ and $n >1$ such that $a^n – b^n$ divides $ a^n + b^n$.

Prove that there are no positive integers $a$ , $b$ and $n>1$ such that $a^{n}–b^{n}$ divides $a^{n}+b^{n}$. Can someone provide me a proof of this and explain it to me please.
0
votes
2answers
30 views

If I have a polynomial $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ with a solution at $x = -1$, how do I get the other root

If I have a polynomial $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ with a solution at $x = -1$, then I know I can just take $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ and divide it by $x+1$ to get the other root. In a ...
1
vote
1answer
34 views

If $p$ is a prime and $p$ divides $a^3$ then $p$ divides $a$ [on hold]

I have to either give a proof or provide a counterexample for this question. $a, b$ are non-zero intergers. If $p$ is a prime and $p|a^3$ then $p|a$ I think this is true but do not know how to go ...
0
votes
4answers
50 views

GCD : Why does the GCD of two numbers divides their difference?

I was working my way through some number theoretic proofs and being a newbie am stuck on this proof : Why does the gcd of two numbers , say (a,b) - also divides their difference : a-b My ...
1
vote
2answers
69 views

The equation $x^4+y^4=z^2$ has no integer solution

The equation $$x^4+y^4=z^2$$ has no integer solution for $(x, y, z), x \cdot y \neq 0 , z >0$. We suppose that there is a solution $(x, y, z)$. We consider the set $$M=\{z \in \mathbb{N} | ...
0
votes
1answer
56 views

Solve $9x^8\equiv 8\pmod{17}$

$$9x^8\equiv 8\pmod{17}$$ Is there a way to solve this with out testing all integers $x$ between $1$ and $17$ ?
0
votes
1answer
36 views

If $p^q - 1$ is a prime, then $p=2$ and $q$ is a prime [duplicate]

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $p$ and $q$ are positive integers ($\mathbb{Z}^+$) such that $q \gt 1$ and $(p^q - 1)$ is ...
0
votes
1answer
18 views

How to use totient function here?

I have asked this before, but I had no idea how to use Totient, now I do here is the questions: How many positive integers $< 2013$ cannot be divided by $2, 3, 5$ ?? An advice given was find ...
1
vote
0answers
23 views

For what positive integer values $b,d$ does $(b^2-d)\mid(b^2-1)?$ hold?

I am curious about the answer to the following questions: And hope that you can help me For what positive integer values $b, d$ does $$(b^2-d)|(b^2-1)?$$ hold? Is it correct that the only ...
1
vote
5answers
186 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
70 views

Proving that $8\mid n(n^{2}-1)(3n+2)$ [duplicate]

I was trying and could not, as it shows that $$8\mid n(n^{2}-1)(3n+2);\forall n \in \text{N}$$ Induction; looking eight consecutive numbers, what to do and how to do?$$$$Sorry, forgot to add a detail: ...
0
votes
4answers
66 views

The divisibility of $a^p-1$ by $a-1$ and by $(a-1)^2$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : Let a $\geq$ 2 and p be any positive integers , then prove that : $(a-1) \mid(a^p - ...
2
votes
1answer
25 views

Find $a$ and $b$ such that $g$ divides $f$ evenly

$f=2X^4-3X^2+aX+b,\ g=X^2-2X+3, \ f,g \in \mathbb{Q}[X]$ I have tried to divide $f$ by $g$ but I get $ (a+10)X +b +3$ as the remainder which looks like a bad result. I have, also, tried to factor ...
0
votes
1answer
38 views

How does the Euler Totient Function apply here?

How many positive integers $< 2013$ are divisible by $2$ Can I somehow use Euler's Totient function to find this?
1
vote
4answers
167 views

$(a,b)=d \overset{?}{\implies} (a^3,b^3)=d^3$

Why is this true? I suspect that its because $\frac{LCM(a,b)^3GCD(a,b)^3}{b^3}=a^3$ and $\frac{LCM(a,b)^3GCD(a,b)^3}{a^3}=b^3$, so it must be the case for $LCM(a,b) \notin R(a,b)$, right?
3
votes
5answers
464 views

Revisted: GCD - $(a,c)=1=(b,c) \overset{?}{\implies} (ab,c)$

How should I show that if $(a,c)=1=(b,c)$ then $(ab,c)$? How should I show that if $a|bc$ and $(a,b)|c$, then $a|c^2$. I think I have the answer, but I'm not sure.
4
votes
2answers
55 views

Suppose $\sqrt2=a/b$, with $gcd(a,b)=1$. Then $3|(a^2+b^2)$ implies that $3|a$ and $3|b$,

Suppose $\sqrt2=a/b$, with $\gcd(a,b)=1$. Then $a^2=2b^2$, so that $a^2+b^2=3b^2$. But $3|(a^2+b^2)$ implies that $3|a$ and $3|b$, a contradiction. I don't understand how $3|(a^2+b^2)$ implies that ...
0
votes
1answer
112 views

Show that if $(a, b) = 1$, $a|c$ and $b|c$, then $(a · b)|c$. [duplicate]

"Show that if $\;(a, b) = 1\;$, $\;a|c\;$ and $\;b|c$, then $(a · b)|c$." $$$$Show: We know that $$x\mid w \;\;\text{and}\;\; y\mid w \Longleftrightarrow \frac{x\cdot y}{(x,y)}\mid w$$So if$$a\mid ...
1
vote
4answers
173 views

$(a^{n},b^{n})=(a,b)^{n}$ and $[a^{n},b^{n}]=[a,b]^{n}$?

How to show that $$(a^{n},b^{n})=(a,b)^{n}$$ and $$[a^{n},b^{n}]=[a,b]^{n}$$ without using modular arithmetic? Seems to have very interesting applications.$$$$Try: $(a^{n},b^{n})=d\Longrightarrow ...
-1
votes
1answer
19 views

Example of GCD=1, but… [on hold]

Give an example of three positive integers $m$, $n$, and $r$, and three integers $a$, $b$, and $c$ such that the GCD of $m$, $n$, and $r$ is $1$, but there is no simultaneous solution to: $x ≡ a ...
0
votes
1answer
45 views

Computing $\mathrm{gcd} (100!, 3^{100})$

I am trying to compute $\mathrm{gcd}(100!,3^{100})$. I am still not sure how to reach an answer but I feel that Wilson's Theorem (i.e., $(p-1)!\equiv -1 \bmod p, p$ prime) and Fermat's Little theorem ...
1
vote
4answers
62 views

Show that if $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$.

Show that if $m$ and $n$ are integers such that $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$. I am not sure where to begin.
0
votes
1answer
45 views

Number Theory Divisibility Question

(From Math Challenge II Number Theory packet) Given that $a,b,n$ are positive integers. Assume that for any positive integer $k\neq b, (k-b)\mid(k^n-a)$, the which of the following must be true? ...
1
vote
2answers
43 views

Proving rigorously that if $3\mid(a+b)$ then $3\mid(a^3+b^3)$ using divisibility definition

Let $a,b\in \mathbb Z$. Prove rigorously using divisibility definition that if $3\mid(a+b)$ then $3\mid(a^3+b^3)$ After a bit of algebra I get that $$3\overset{?}{\mid}(a+b)^3-3ab(a+b)$$ So now how ...
0
votes
4answers
75 views

$\gcd(4n+1, n+2)$ is found in what sense?

What is the gcd of these two numbers? Is it possible to find the gcd? It should be $1$ when $n=1$, but $3$ when $n=5$. $4n+1 = (3)(n+2) + (n-5)$ <-- This step is only valid when $n \geq 5$ How do ...
2
votes
0answers
65 views

Prove that if $d_1=\gcd(a,b), d_2=\gcd(b,c), d_3=\gcd(c,a), D=\gcd(a,b,c)$, and $L=\operatorname{lcm}(a,b,c)$, then $L= \frac{abcD}{d_1 d_2 d_3}$

I tried to define: $a=d_1x_1$, $b=d_1y_1$; $b=d_2x_2$, $c=d_2y_2$; $c=d_3x_3$, $c=d_3y_3$. then $\operatorname{L.H.S} =d_1d_2d_3x_1x_2x_3=d_1d_2d_3y_1y_2y_3$ $\implies$ $x_1x_2x_3=y_1y_2y_3$; ...
0
votes
0answers
30 views

Finding how many divisors a number has between two given values

I need to find how many divisors a number has between two given values, including 1 if it is in range, and including both of these values. Let us denote it as D(n,a,b), where n is the number, a is ...
2
votes
3answers
127 views

Prove that distinct Fermat Numbers are relatively prime [duplicate]

The Fermat numbers are defined by $F_m = 2^{2^m} + 1$. Prove that for $m \ne n$ we have $(F_m, F_n) = 1$. I have to first prove that $F_{m+1} = F_0F_1 \cdots F_m + 2$ by representing $F_{m+1}$ in ...
1
vote
3answers
286 views

The gcd of $p+q$ and $p-q$ where $p4 and $q$ are distinct odd primes

Suppose $p$ and $q$ are distinct odd primes. Prove that $\gcd(p+q, p-q) = 2$. I had figured out that $d$ divides $2p$ and $d$ divides $2q$, but I did not recognize to use coprimeness and ...
1
vote
2answers
246 views

“Quadly” numbers with just 4 factors

A positive integer with exactly four positive factors is called "quadly". Compute the least $n$ for which each of $n,n+1$ and $n+2$ is quadly. (ARML 2008) My method of attacking this problem started ...
1
vote
2answers
30 views

How to recognise the digit multiplication, subtraction or addition when checking for divisibility by 7, 11, 13, 17 and 19?

I was studying this page Divisibility by prime numbers under 50 to check for the divisibility by 7, 11, 13, 17, 19 etc. Is there any way to recognise whether to add or sub the given times of unit ...
3
votes
1answer
79 views

Any $p + 1$ consecutive integers contain at least two invertible elements modulo $p!!$ if $p$ is odd

I am trying to prove the following: $p + 1$ consecutive integers contain at least two invertible elements modulo $m = 3 \cdot 5 \cdots ( p - 2 ) \cdot p$, where $p$ is odd. I shared my idea ...
-1
votes
1answer
52 views

On no. of solutions of product of positive integers equal to sum [on hold]

$n \ge 2$ be an integer , let $a(n)$ be the no. of solutions in positive integers of $x_1+x_2+...+x_n=x_1x_2...x_n ; x_1 \le x_2 \le ... \le x_n$ , then is it true that $a(n+1)=1 \implies n$ is ...
3
votes
0answers
45 views

Multiple of $n$ and the sum of its digits is $k\geq n$.

Show that for every positive integers $k\geq n$, with $n$ not divisible by $3$, there is a positive integer divisible by $n$ and such that the sum of his digits is $k$.
4
votes
3answers
165 views

What is so great about 7?

I'm going to write down my problem verbatim: Write down the integers from $1$ to $50$ in rows of $10$ numbers each. Mark out $1$, and then cross out all multiples of $2$ greater than $2$ ...
0
votes
3answers
25 views

Solving for mod indirectly

How many positive integers $n$ exist such that $\frac{680}{n}$ is an integer? So, this is quite obvious, $680 \equiv 0 \pmod{n}$ How should I solve for $n$? There will be multiple $n$?