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
52 views
0
votes
1answer
33 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) ...
20
votes
4answers
1k views

Is the number 333,333,333,333,333,333,333,333,334 a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
4
votes
2answers
50 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 ...
4
votes
2answers
61 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 ...
0
votes
2answers
61 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.
0
votes
1answer
41 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 ...
4
votes
5answers
117 views

Show that $\gcd(a,b)>1$

Given are three natural numbers $a$, $b$ and $c$, for which $$\frac1a+\frac1b=\frac1c,$$ show that $\gcd(a,b)>1$. Could you someone provide a hint? I already tried algebraic manipulation, but ...
0
votes
1answer
45 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.
4
votes
2answers
111 views

If $3\mid a,b,c$ and $n=a^2+b^2+c^2$, prove that there exist $x,y,z$ such that $n=x^2+y^2+z^2$, where $3\nmid x,y,z$.

If $3\mid a,b,c$ and $n=a^2+b^2+c^2$, prove that there exist $x,y,z$ such that $n=x^2+y^2+z^2$, where $3\nmid x,y,z$. Here $n\in\mathbb N$, $a,b,c,x,y,z\in\mathbb Z$. This problem is originally ...
0
votes
2answers
32 views

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

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.
0
votes
3answers
952 views

calculate GCD of very large integers

How i can calculate GCD of two very large integers for example: gcd(31415926534676736647, 438478473847834834784748) either by hand or computer? is there any ...
2
votes
3answers
27 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 ...
12
votes
1answer
196 views

Family of GCDs all equal to $2$

Is it true that $$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2$$ for all $n \in \mathbf{Z}_{\geq 0}$? I'm continually stumped with this and verifying it numerically is quite expensive very ...
-1
votes
0answers
31 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
2
votes
2answers
82 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 ...
1
vote
1answer
22 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{ ...
0
votes
1answer
45 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
0answers
22 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
2answers
87 views

gcd multiplied by lcm

I've encountered a very confusing problem in my homework. Let a and b natural numbers. Then, let x = gcd(a,b) * lcm(a,b). The question asks what [number] is x below, in terms of a and b. I do not ...
1
vote
2answers
44 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
43 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 ...
3
votes
4answers
84 views
1
vote
1answer
58 views

If $a,b,c,d\in\mathbb N$ and $a^2+b^2\mid ac+bd$, can it be true that $\gcd(a^2+b^2,c^2+d^2)=1$? or $3$? or $74$?

If $a,b,c,d\in\mathbb N$ and $a^2+b^2\mid ac+bd$, can it be true that $\gcd(a^2+b^2,c^2+d^2)=1$? or $3$? or $74$? That problem is complicated. I've tried some approaches, but they're useless. ...
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
21 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
vote
1answer
33 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 ...
1
vote
1answer
25 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
64 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
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
22 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$? ...
1
vote
1answer
80 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
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 ...
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 ...
2
votes
1answer
213 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
2answers
33 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
24 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?
0
votes
1answer
11 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
53 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
18 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 ...
5
votes
4answers
69 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
1answer
29 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 ...
3
votes
1answer
59 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 ...
5
votes
3answers
57 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
104 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
61 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 ...
0
votes
3answers
66 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 ...
2
votes
2answers
73 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
62 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 ...
0
votes
3answers
74 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 ...