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
79 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
4answers
101 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
18 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)}$
3
votes
0answers
39 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$ ?
2
votes
1answer
57 views

The greatest common divisor is the smallest positive linear combination

How to prove the following theorems about gcd? Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$. ...
1
vote
1answer
36 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
52 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
44 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
25 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
103 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
27 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
36 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
100 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
242 views

If $\gcd(\gcd(a, b),\gcd(a, c))=1$, then $\gcd(a, bc) = \gcd(a, b) \cdot \gcd(a, c)$

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
91 views

Using Extended Euclidean Algorithm for $85$ and $45$

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
29 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
53 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
12 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
55 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!
2
votes
1answer
34 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
61 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
129 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
65 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
73 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 ...
5
votes
4answers
70 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
85 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
65 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 ...
6
votes
4answers
97 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
87 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
36 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
43 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
75 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
36 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
37 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
45 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
47 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 ...
2
votes
2answers
64 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
58 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.
2
votes
3answers
75 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
42 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
36 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 ...
3
votes
3answers
119 views

when ${\rm gcd} (a,b)=1$, what is ${\rm gcd} (a+b , a^2+b^2)$?

I want to prove above statement "what is ${\rm gcd} (a+b , a^2+b^2)$ when ${\rm gcd}(a,b) = 1$" I've seen some proofs of it, but i couldn't find useful one. here is one of the proof of it. some ...
0
votes
5answers
49 views

Solving -2A - 2B = 2

I should know this, but when simplifying $$-2A - 2B = 2$$ When I divide the LHS by 2, do I divide -2A AND -2B or just one of them? I always thought you did one of them, and then the next. So order of ...
0
votes
6answers
67 views

Prove that if $\gcd (m,n)=1$ and $m\mid x$ and $n\mid x$, then $mn\mid x$.

I've come across the statement that if $\gcd (m,n)=1$ and $m\mid x$ and $n\mid x$, then $mn\mid x$. (This is needed for a proof of the correctness of RSA that I have been given.) I can't see how to ...
3
votes
2answers
93 views

How to explain why 10/0 is an okay grade book entry?

I usually record class grades in my grade book in a format like 9/10, where "9" means how many points a student earned and "10" means how many points they could possibly earn. The computer grade book ...
0
votes
1answer
32 views

N is a number in base 9.Find N when n is divided by 8(in base 10)?

N is a number in base 9.Find N when n is divided by 8(in base 10)? And N can be very large.say N=32323232.....50 digits This can be done by converting N to base 10.But time consuming. What will be ...
0
votes
2answers
50 views

If $c | ab$, then $c | a$ or$ c | b$

I need help proving/disproving the implication, If $c | ab$, then $c | a$ or $c | b$ So far, I got Assume $c | ab$ then $ab= cl$ for some integer $l$ Now what should my next step be?
2
votes
1answer
55 views

Divisibility Property

I am trying to justify the following result: Let $p,q$ be integers such that $GCD(p,q) = 1$. Then for all $n \in \mathbb{N}$ exists an integer $j_n$ such that $q^{j_n}t = t \ (mod \ p^{2n+1}), \ ...