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
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
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$? ...
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
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
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
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) ...
2
votes
3answers
65 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
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
1answer
56 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
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?
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
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 ...
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 ...
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 ...
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
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 ...
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 ...
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
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 ...
0
votes
3answers
32 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
74 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
27 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
34 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
35 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
45 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
53 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
57 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
72 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
40 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
20 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
99 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
48 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
63 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
78 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
20 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
46 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
48 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}), \ ...
0
votes
4answers
60 views

Is there a counterexample to “For all integers $a,b, d$, if $d\mid(3a+2b)$ and $d\mid(2a+b)$, then $d\mid a$ and $d\mid b$.”

I've tried to solve this problem, but I keep getting stuck at the end. Assume $a, b$ , and d are integers and $d$ $\neq$ 0. $3a+2b = dm,\,\,\,$ for some integer $m$. $2a+b = dn,\,\,\,$ for ...
3
votes
2answers
81 views

Divisibility property of $(a+b)^n-a^n-b^n$

Let $n$ be a natural number of the form $n=6k+1$ (while $k$ is a positive integer). Show that $(a^2+ab+b^2)^2$ divides $(a+b)^n-a^n-b^n$ for all integer numbers $a,b$ (such that $a^2+ab+b^2\ne0$).
2
votes
2answers
86 views

Find all primes of the form $2^{2^n} + 5$ for a nonnegative integer n

I'm a little lost on how to do this problem. It looks a lot like the definition for the Fermat numbers: $F_n = 2^{2^n} + 1$, however I'm not sure how to use that in order to find all of the primes of ...
1
vote
1answer
59 views

Divisibility !?? wihout mathematical induction if possible PLZ …

Hello I need to prove if $n\, |\, (x-a)$ and $n \, | \, f(x)$ then $n \, | \, f(a)$. It is true if $\operatorname{deg}(f)=1$ or $2$, but what for greater degree of $f(x)$? I don't know how to ...