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
1answer
17 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
8 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
43 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
37 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
18 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
67 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
16 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$ ?
0
votes
0answers
20 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
26 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
62 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 ...
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
99 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
20 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
50 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
11 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
22 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
96 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
2answers
58 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
29 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
66 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 ...
-2
votes
1answer
28 views

How to use Euclid's algorithm to prove a statement? [closed]

By using Euclid's extended algorithm prove that if $q$ is a divisor of both $b$ and $c$ then $q$ divide $\gcd(b, c)$.
1
vote
0answers
25 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
67 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 ...
0
votes
3answers
30 views

Greatest common divisor of a number and the same number multiple of some rational

I want to simplify (e.g. in terms of prime factors and its exponents) given expression: $$ \gcd\left(a, a \frac{b}{c}\right), $$ where $c\mid ab$. Is it possible? Thanks!
1
vote
1answer
41 views

Finding the set {$ a\ |\ \mathrm{gcd}(a, b) = 1$}

I was wondering about the method to determine the set {$ a \ |\ \mathrm{gcd}(a, b) = 1$} : what is the faster way to get it ? I was thinking about to compute it like the sieve of Eratosthenes : test ...
1
vote
0answers
71 views

Any general hints on how to prove that two functions$\ f(n)$ and$\ g(m_1,m_2,…,m_{28})$ never have a common natural divisor?

All the variables are natural numbers. I'm not asking for a proof, since while we simply have$\ f(n)=n^3-n+1$,$\ g$ is a very long sum of cube roots (which contain square roots as well). I'm after ...
1
vote
2answers
23 views

How can I prove divisibility using congruence?

I'm new to this, so please excuse me if I said something wrong or offended anyone. We're doing the number theory in class, and I came across this question, which I had no idea how to even begin..: ...
0
votes
1answer
33 views

If and only If involving divisibility

If $a$, $b$, and $n$ are positive integers, prove that $a^n|b^n$ if and only if $a|b$. So far I've done one way of the proof... I've proved that if $a|b$, then $b=ak$, $k$ is an integer, then ...
2
votes
1answer
34 views

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$. proof: Suppose $\sigma(p^k) = [p^{k+1} -1]/(p-1) = n$. Then $n-1 = [p^{k+1} -1]/(p-1) - 1= [p^{k+1} -1 - (p-1)] /(p-1) = [p^{k+1} - ...
1
vote
1answer
42 views

Divisibility and Primes

Suppose that $p,q,r$ are prime numbers and $p$ is odd. If $p\,|\,(2q+r)$ and $p\,|\,(2q-r)$, prove that $q=r$. So I'm trying to use the definition of greatest common divisor to come up with two ...
1
vote
1answer
47 views

How to prove that $(p-1)^2$ $\mid$ $(p-1)!$ when $p$ is a prime number and $p>5$?

I say that $p-1$ $\mid$ $(p-1)!$ then I want to prove that $p-1$ $\mid$ $(p-2)!$. I started by saying that $p-1$ is an even number so $2\mid (p-1)$ and that means that $\frac{p-1}{2}$ is an integer. ...
3
votes
4answers
55 views

Prove that $\gcd (n^3-1,n+1)=1$ for all even $n$.

Prove that if $n$ is even, then $$\gcd(n^3-1,n+1)=1.$$ I really don't have a clue with this one. Any help would be appreciated.
1
vote
3answers
60 views

Divisibility by primes

Suppose that $n$ is a natural number, $n \ge 2$, and $n$ satisfies: For each prime divisor $p$ of $n$, $p^2$ does not divide n. If $p$ is prime, $p$ divides $n$ if and only if $(p − 1)$ divides $n$. ...
1
vote
1answer
35 views

Fermat's Little theorem to find primes

Find $4$ primes that divide $14^{60} - 33^{60}$ okay, so the easiest thing to do was to re-write that as $7^{60}2^{60} - 11^{60}3^{60}$. However, that doesn't really help. Next step is the ...
0
votes
2answers
17 views

GCD(m,n) = sm + tn proof

Suppose that m and n are positive integers and that s and t are integers such that gcd(m,n) = sm + tn. Show that s and t cannot both be positive or both be negative. I understand that if both of them ...
-4
votes
1answer
60 views

Is 6m(2m +10) divisible by 4? [closed]

Is $6m(2m +10)$ divisible by $4$? What is the reason for this, assuming all variables are integers?