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
1answer
27 views

Proving property of congruence - help needed

Let $c,d,m,k ∈ \mathbb{Z}$ such that $m ≥ 2$ and $k$ is not zero. Let $f = \gcd(k,m)$. If $c \equiv d \pmod m $ and $k$ divides both $c$ and $d$, then $$ \frac{c}{k} \equiv \frac{d}{k} ...
4
votes
2answers
43 views

If for all $n\in\Bbb{N}, a^n-n$ divides $b^n-n$ then $a=b$.

Exercise: Let $a,b\in\Bbb{N}$, show that if for all $n\in\Bbb{N}, \quad a^n-n$ divides $b^n-n$, then $a=b$. I don't have lot of knowledge on this subject, I am aware about some elementary result ...
0
votes
2answers
19 views

Proof involving greatest common divisor [on hold]

Suppose that $\text{gcd}\:(a, y) = 1$ and $\text{gcd}\:(b, y) = d$. How do I show that $\text{gcd}\:(ab, y) = d$?
1
vote
2answers
36 views

How can I prove that the square root of two prime numbers multiplied is non-rational number?

$P$ and $Q$ are two distinct prime numbers. How can I prove that $\sqrt{PQ}$ is an irrational number?
0
votes
2answers
45 views

Find all natural numbers n for which $3^n + 5^n$ is divisible by $3^{n-1} + 5^{n-1}$

Find all natural numbers n for which $3^n + 5^n$ is divisible by $3^{n-1} + 5^{n-1}$. Interested if there is a nice quick way other than mine.
-1
votes
1answer
23 views

Set of a summation

Let $S = \{n ∈ N | n \text{ divides the sum of any n consecutive numbers} \}$. How can I describe the set S? I was given the hint: $\displaystyle\sum\limits_{n=1}^N n=\frac{N(N+1)}{2}$ I don't want ...
0
votes
1answer
28 views

Greatest Common Divisor of two binary polynomials

How can I find the GCD of $x^4 + x^3 + x^2 + 1$ and $x^6 + x^5 + x^4 + x^3 + x^2 + 1$? I know that $x^4 + x^3 + x^2 + 1$ is an irreducible polynomial of degree $4$, and that it is not primitive, but ...
3
votes
2answers
52 views

If $(a^2+b^2) \mid (c^2+d^2)$ and $\gcd(a,b)=\gcd(c,d)=1$ and $\gcd(a,c)>1$, what can be said about the components?

While working on a divisibility problem in integers $a,b,c,d$, with $\gcd(a,b)=\gcd(c,d)=1$, I've come up against the hypothetical condition $$ (a^2+b^2) \mid (c^2+d^2), \tag{$\star$} $$ where, also ...
1
vote
2answers
31 views

For any integer a, if $6|(3−a)$, then $3| (a−2)$.

Prove: For any integer a, if $6|(3−a)$, then $3| (a−2)$. I've been trying to work this problem for a while, but missed a day of class and can't seem to work it out.
2
votes
3answers
21 views

Prove if a|c and b|d and gcd(c,d)=1 then gcd(a,b)=1

I'm trying to prove that if a|c and b|d and gcd(c,d)=1 then gcd(a,b)=1 So far, I have assumed that: Since gcd(c,d) = 1 then by EEA, gcd(c,d) = 1 = cx + dy for some x,y that are integers. And since ...
2
votes
2answers
70 views

Probability a product of $n$ randomly chosen numbers from 1-9 is divisible by 10.

I'm working on a problem where each number is chosen randomly from 1-9. Given $n$ numbers chosen in this manner, we multiply all of these together. I'm looking for the probability that this product is ...
0
votes
0answers
28 views

Equation with gcf , lcm

Can you please help me with this? I have no idea how to solve this problem Find all positive integers $a$, $b$ such that $$a+b+\gcd(a,b)+\text{lcm}(a,b)=50$$ Thank you for answer
1
vote
1answer
20 views

if $p=(a+ib)(c+id)$ and $p^2 = a^2 + b^2$ then $p\mid a$ & $p\mid b$

We're working on Gauss integers... p is an odd prime such that $p \not\equiv 1 \pmod 4$. We want to prove that if there is $(a,b,c,d) \in \mathbb{Z}^4$ such that $$p = (a+ib)(c+id) \text{ ...
1
vote
0answers
13 views

Using divisibility and greatest common divisor for a proof

If u|t and v|t and gcd(u,v)=1, then prove that (uv)|t I started by analyzing the definition of divisibility and I got that (uv)|t^2, but this doesn't help me. Any advice would be appreciated. Thank ...
0
votes
1answer
41 views

If a|b and b|a, find the value of a in terms of b.

If a|b and b|a, where a and b are integers and a≠0, find the value of a in terms of b. Assume that b>0.
0
votes
1answer
44 views

Is it possible to find $n-1$ consecutive composite integers

Given an integer $n\geq 2$ ,can we always find an integer $m$ such that each of the $n-1$ consecutive integers $m+2,m+3,.....,m+n$ are composite?
1
vote
2answers
42 views

Which of the following numbers does not divide $2^{1650}-1$?

I'm practicing for a math competition that is coming up, and I got stuck on this question: Which of the following numbers does not divide $2^{1650}-1$? $3$, $7$, $31$, $127$, $2047$ I've seen a ...
1
vote
2answers
23 views

Algorithm to find the coefficient of GCD linear combination?

One of the properties of the GCD of two integers is that it can be written as the linear combination of the two, is there an algorithm that can be used to find the coefficients of this linear ...
2
votes
5answers
74 views

How to prove that $8^{18} - 1$ is divisible by $7$ [duplicate]

How to prove that: $$ 8^{18}-1\equiv0\pmod7 $$ In the simplest way?
0
votes
0answers
16 views

Proof with GCD(m, n) [duplicate]

How can I prove that equation below is true? If $a > b$ and $a, b$ are relatively prime numbers, then for $0 <= m < n$: $GCD(a^n - b^n, a^m - b^m) = a^{GCD(m,n)}-b^{GCD(m,n)}$
1
vote
0answers
18 views

GCD-Domain and proprieties

Let $A$ be a commutative GCD-domain (not necessary UFD or Bezout) and $a,b,c$ elements of $A$ such that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$. Is it true that $\gcd(ab,c) = 1$ ?
-1
votes
0answers
23 views

Range divisibility of large numbers

Question: Consider a range of positive integers from $[L,R]$ and a set of other positive integers $A = \{\ldots\}$. Find the number of integers in $[L,R]$ that are divisible by any of the ...
1
vote
1answer
27 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
0
votes
1answer
23 views

How can I show that the following number is not divisible by $p$ prime?

Let $p$ be a prime number. Let $k$ be some natural number and $r$ be some nonnegative integer. Then, I want to show that for $1\leq i\leq p^k-1$, \begin{equation*} \frac{p^{k+r}m-i}{p^k-i} ...
2
votes
3answers
48 views

How to prove that $\gcd(2n+3, 3n+1)$ divides $7$?

How can I start proving that gcd(2n+3, 3n+1) | 7? EDIT: It is $\gcd(2n+3, 3n+1)$ divides $7$. My bad. Thanks paw88789.
0
votes
3answers
17 views

Possible remainder when multiple of a number is divided by multiple of the same dividor

I have a couple of questions regarding which I am confused. $1)$ What is the Greatest, Positive Integer $n$ such that $2^n$ is a factor of $12^{10}$ $(3\cdot 2^2)^{10}$ So, my guess is $n = 12$? ...
0
votes
1answer
21 views

Find all $(h,k)$ such that $2^h \equiv 1 ~(\text{mod}~ 3^k) $

I'm facing with the following problem: Find all $(h,k)$ such that $$2^h \equiv 1 ~(\text{mod}~ 3^k) ~~~~~~~~(1)$$ and $$2^h \geq 3^k+1 ~~~~~~~~(2).$$ I'm just able to prove that the $(1)$ holds ...
1
vote
1answer
65 views

Product of roots of unity

Does somebody have a nice proof of the following? $$\prod_{m=1}^{n-1} \frac{e^{2\pi i k m/n} - 1}{e^{2 \pi i m / n} - 1} = \begin{cases} 1 & \text{ if $\gcd(k, n) = 1$} \\ 0 & ...
0
votes
1answer
14 views

Determine whether or not a binary number is divisible by $3$

Let $K$ be a natural number with $n$ binary digits. Is there an $O(n)$ method for deciding whether or not $K$ is divisible by $3$? $3|K \iff d_1-d_2+d_3-d_4\dots\pm d_n=0$ works correctly up to ...
0
votes
1answer
31 views

Primitive polynomial and divisibility

Let $f(x) \in \mathbb Z[x]$ with $c(f)=1$ and $f$ is non-constant. Now suppose $h(x) \in\mathbb Z[x]$ be such that $h(x)=f(x)q(x)$ where $q(x) \in\mathbb Q[x]$. Then I have to show that $q(x) ...
2
votes
3answers
58 views

$\dfrac1a+\dfrac1b=\dfrac1c$, $a, b, c \in \mathbb{N}$ with no common factor, find all solutions [duplicate]

Given $\dfrac1a+\dfrac1b=\dfrac1c$, where $a, b, c \in \mathbb{N}$ with no common factor, find all solutions. Actually, you can think this question as a follow up of this one. Today, I saw this ...
2
votes
1answer
195 views

two $\gcd$s that are coprime

Let $a, b$ and $c$ be integers. Prove that if $\gcd(a, b)$ and $\gcd(a, c)$ are coprime, then $\gcd(a, bc)$ = $\gcd(a, b) · \gcd(a, c)$ I am stumped in this problem. Can anybody clarify me what ...
1
vote
1answer
31 views

Using Extended Euclidean Algorithm

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have ...
0
votes
1answer
19 views

Divisibility Test Question of Curisosity

Why do we only do divisibility tests up to 11? At least, in my proofs class and in my textbook, that's all it goes up to: 11. Can anyone explain?
1
vote
2answers
25 views

Elementary Number Theory: Divisibility proof

Let $k,m,n \in N\setminus \{0\}$, s.t. $n=k\cdot m$. Show that $k$ is odd $\Rightarrow ∀ a,b \in Z: (a^m+b^m) \mid (a^n+b^n)$ In the first part of the task, I have already shown that $∀ a,b \in Z: ...
0
votes
1answer
10 views

Handing out coupons problem

I am trying to make an equation in excel but I can come up with it. I am handing out coupons to people. Everyone will get 1,2 or 3 coupons. I know how many people and how many coupons I have used. ...
2
votes
2answers
51 views

Show that $\gcd(3n,3n+ 2) = 1$ when $n$ is odd

I would like to know why $\gcd(3n,3n+ 2) = 1$ when $n$ is odd. I tried to use the Euclidean Algorithm, but I got confused: $$ 3n+2 = 3n + 2$$ $$3n = \ ? $$ Thanks!
0
votes
0answers
12 views

How to convert a Timestamp to fractional time (decimal)

If I have a timestamp 20114-4-1 13:24:10 what is the formula to convert this to a fractional time? I am trying to create a comparison between dates and I would like to do this using decimal. I have ...
2
votes
1answer
26 views

If (a,b) = 1 and c|(a+b), show that (a,c) = (b,c) = 1

I am working on this homework problem: If $\gcd(a, b) = 1$ and $c|(a + b)$, show that $\gcd(a, c) = \gcd(b, c) = 1$. Hint: Let $d = \gcd(a, c)$ and show that $d|\gcd(a, b)$. (An Introduction to ...
5
votes
3answers
45 views

Show some polynomial is irreducible over the field of 7 elements.

I have to show that the polynomial $x^4+x^3+x^2+x+1$ is irreducible over the field $F_7$. It doesn't have roots in $F_7$, but I can't show it does not have degree two irreducible factors in $F_7[x]$. ...
1
vote
4answers
97 views

$\gcd(p, (p-1)!) = 1$?

Let $p$ be a prime number. Prove that $\gcd(p, (p-1)!) = 1$. I've attempted using the definition of $\gcd$ to solve this, but I haven't reached a conclusion. Any ideas?
2
votes
1answer
60 views

$a^n\mid b^n$ if and only if $a\mid b$.

Suppose $a$, $b$, $n$ are positive. Prove that $a^n\mid b^n$ if and only if $a\mid b$. I know that this can be proved through prime factorization, but I want to prove it using other methods. I ...
2
votes
0answers
36 views

Applications of the Extended Euclidean Algorithm

I am asked to prove the statement: If $k$ is a common divisor of $a$ and $b$, then $k|gcd(a,b)$. I am also required to prove the converse. We can assume that $a, b, k$ are non-zero integers. I have ...
0
votes
3answers
65 views

Is $\frac{4n^2+4n+1}{8}$ an integer for any $n\in \mathbb{N}$?

I've been thinking the following: $8|4n^2$ for some $n$ and $8|4n$ for some $n$, which would imply that there are $q_1,q_2\in \mathbb{Z}$ such that $4n^2=8q_1$ and $4n=8q_2$, the only solution for ...
4
votes
4answers
65 views

If $(a,b)=1$, prove that $(a^2+b^2,a+b)=1$ or $2$.

If $(a,b)=1$, prove that $(a^2+b^2,a+b)=1$ or $2$. So far, I let $d=(a^2+b^2,a+b)$ $\implies d|(a^2+b^2-(a+b)^2)$ $\implies d|(a^2+b^2-(a^2+2ab+b^2))$ $\implies d|(-2ab)$ I have heard from other ...
2
votes
2answers
68 views

Proving that if $p$ is a prime number then $gcd (p, (p-1)!) =1$

I am just making sure whether this is a valid proof: Since $p$ is a prime number, then $p$ is only divisible by $1$ or $p$ Suppose we want to take the $gcd (p,a)$ with a, an arbitrary ...
0
votes
2answers
58 views

Quick way to find the GCD of 7602 and 7710

I've been reading through my book and I see that to find the GCD of these two numbers, I can look at the difference of these two numbers. However, how do I determine the GCD from the difference? I've ...
3
votes
1answer
50 views

Divisibility of polynomials in a subfield of a field.

I am trying to prove the following assertion: Let $K\subset L$ be fields, let $f,g\in K[x]$ be such that $f\mid g $ in $L[x]$, then $f\mid g$ in $K[x]$. We clearly have that $fh=g$ for some ...
1
vote
0answers
28 views

Prove that $10 | (n^a - n^b)$.

$n$ is a positive integer. Prove that there exists positive integers $a$ and $b$, $(a > b)$ such that $10 | (n^a - n^b)$. I have tried to prove this by induction on $n$, but I get stuck at the ...
0
votes
3answers
71 views

Prove that $\gcd(abc + abd + acd + bcd, abcd) = 1$

Let $a, b, c, d \in \mathbb Z$. Prove that $\gcd(abc + abd + acd + bcd, abcd) = 1$ if and only if $a, b, c, d$ are pairwise relatively prime. I am very confused as to how I should even start this ...