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)

3
votes
3answers
226 views

Why are all non-prime numbers divisible by a prime number?

In Euclid's infinite prime numbers proof, the logic is as follows: Assume a set $S$ of all prime numbers in existence is finite (there are a finite amount of primes) Then there must be a greatest ...
2
votes
1answer
41 views

Silly number theory questions I can't prove.

I know if $gcd(r,s)=1$ then $1=as+bs$ for some intgers $a,b$. Here's what I want to know: which numbers can be written as $as+bs$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
0
votes
0answers
44 views

Prove that $l = k/\gcd(m,k)$.

Suppose $ml = kt$ where $t$ is an integer and $m<k.$ $\implies k~|~ml$ $~~~~~$and $~~~~~$ $1 \leq \gcd(m,k) \leq m$ $\implies \dfrac{k}{\gcd(m,k)}~\Big|~\left(\dfrac{m}{\gcd(m,k)}\right)l$ What ...
2
votes
0answers
17 views

proof of: $\gcd(n^a - 1, n^b - 1) = n^{\gcd(a,b)}- 1$ [duplicate]

I have a problem with following proof: $$\gcd(n^a - 1, n^b-1) = n^{\gcd(a,b)} - 1 $$ The only thing that I can show is fact: $$n^{\gcd(a,b)} -1 | n^a - 1$$ $$n^{\gcd(a,b)} -1 | n^b - 1$$ And ...
7
votes
3answers
413 views

If $R$ is a commutative ring with identity, and $a, b\in R$ are divisible by each other, is it true that they must be associates?

Thank you very much! My problem is: If $R$ is a commutative ring with identity, and $a, b$ are its elements that are divisible by each other, is it true that they must be associates? Here, $a$ ...
8
votes
3answers
379 views
+50

How does one attack a divisibility problem like $(a+b)^2 \mid (2a^3+6a^2b+1)$?

In my current line of investigation, I am running into [many] divisibility questions like the one in the title, i.e. $$ (a+b)^2 \mid (2a^3+6a^2b+1), \qquad(\star) $$ where $a > b \ge 1$ are ...
17
votes
4answers
456 views

Do there exist infinitely many pairs of primes $(p,q)$ such that $pq$ divides $2^{p-1}+2^{q-1}-2$?

A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:- Do there exist infinitely many pairs of primes $(p,q)$ such that ...
1
vote
1answer
47 views

When is a sum of products of positive powers of 2 and 3 divisible by $2^b-3^n$?

Here we have a really tough exercise. Find all natural solution: $$\frac{\sum\limits_{k=1}^n 2^{a_k} 3^{n-k}}{c}+3^n=2^{b} ,\quad b\geq a_n; \quad a_k, b, c ,n\in \mathbb N $$ Any ideas, hints?
1
vote
1answer
171 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
10
votes
5answers
2k views

Disproving the claim that the numbers 1+2+4, 1+2+4+8, 1+2+4+8+16… alternate between prime and composite

I am working through an elementary number theory book and I have come across the following problem. Show the following claims are wrong: Claim 1: The sequence 1+2+4, 1+2+4+8, 1+2+4+8+16, ...
4
votes
2answers
80 views

A non-UFD such that $a^2 \mid b^2$ does not lead to $a\mid b$

Is there any non-UFD that is a commutative ring such that $a^2 \mid b^2$ does not always lead to $a\mid b$? It would be preferable if examples are something that does not involve ...
4
votes
4answers
218 views

What is easiest way to know it the large number divisible by 57

What is the easiest way to know if large number is divisible by 57? For example, how could I deduce that 57 divides 300000177?
2
votes
4answers
73 views

Prove that $133$ divides $11^{n+1} + 12^{2n−1}$ for all $n > 1$? [duplicate]

I have tried this question so hard but still stuck here. It seems like easily provable if all $n$ are all positive numbers but in this question, the $n$ is bigger than $1$. original question : prove ...
2
votes
1answer
98 views

When does $2^n+n \mid 8^n+n$?

How to find all positive integers $n$ such that $2^n+n$ divides $8^n+n$ ?
1
vote
4answers
25 views

How to find a modular multiplicative inverse when GCD is not 1

I am working on a problem that requires finding a multiplicative inverse of two numbers, but my algorithm is failing for a very simple reason: the GCD of the two numbers isn't 1. I figured I must've ...
1
vote
7answers
50 views

$\operatorname{gcd}(ab,a+b)=1$ if $a$ and $b$ are relatively prime

I'm trying to show that if $\operatorname{gcd}(a,b) = 1$, then $\operatorname{gcd}(ab,a+b)=1$. I've tried to use the gcd properties: $$\operatorname{gcd}(a,b)=1 \implies ...
2
votes
3answers
148 views

Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
9
votes
1answer
101 views

For what integers $n$ is this divisibility statement true?

The statement being $$n^2 + 2 \mid 2014n + 2$$ The answer is $n = -2, 0, 1, 2014$. Don't know how to arrive at this answer without using comp sci. (Using the compsci answer, we can restrict the ...
3
votes
2answers
91 views

Fastest way to find if a given number is prime

Given a random number, what would be the quickest possible way of finding out whether it was prime? Obviously, one could just iterate through the number in order to see if it was divisible by ...
4
votes
1answer
56 views

Show that each integer of the form $a^2+b^2$ has all the factors of this form, where $(a, b)$ are distinct integers and relatively prime

Show that each integer of the form $a^2+b^2$ has all the factors of this form, where $(a, b)$ are distinct integers and relatively prime Progress If $a^2+b^2$ is prime then it is already proved, ...
2
votes
1answer
22 views

prove by contradiction that $ax+by=c$ has no integer solutions if $c$ does not divide into $\gcd (a, b)$

Prove by contradiction that (the diophantine equation) $ax+by=c$ has no integer solutions if $c$ does not divide into $\gcd (a, b)$. Here is what I did: lets assume $c$ divides into $\gcd (a, b)$. ...
2
votes
2answers
25 views

Prove that the Diophantine equation $ax+by=c$ has no integer solutions if $\gcd(a,b)$ does not divide $c$

Prove that the Diophantine equation $ax+by=c$ has no integer solutions if $\gcd(a,b)$ does not divide $c$ there was a hint which is use use contradiction.
2
votes
1answer
40 views

How prove $n|2^{\frac{n(n-1)}{2}}\cdot (2-1)(2^2-1)(2^3-1)\cdots (2^{n-1}-1)$

Question: Today, when I solve other problem, I found this follow interesting result $$n\mid\left(2^{\frac{n(n-1)}{2}}\cdot (2-1)(2^2-1)(2^3-1)\cdots (2^{n-1}-1)\right),n\ge 1$$ It is clear ...
1
vote
1answer
37 views

If $n$ is any positive integer whose last digit is $5$, then $5$ divides $n$

Prove that if n is any positive integer whose last digit is a 5, then 5|n Therefore, n is going to be 5, 15, 25, 35 etc ... b∣a states that 'b divides a' and we know that 5∣5, 5∣15, 5∣25, 5∣35 ...
6
votes
3answers
92 views

If $n=3^{2^k}-2^{2^k}$, then $n\mid 3^{n-1}-2^{n-1}$

Let $k \in \mathbb{N}$ and let $n=3^{2^k}-2^{2^k}$. Show that $$n\mid 3^{n-1}-2^{n-1}.$$ I have no idea how to prove this. Any suggestions?
-2
votes
1answer
57 views

The greatest common divisor of several numbers is the least positive integer that is their linear combination [closed]

Problem Show that the greatest common divisor of the integers $a_1, a_2, ..., a_n$, not all $0$, is the least positive integer that is a linear combination of $a_1, a_2, ..., a_n$. Remarks The ...
5
votes
2answers
172 views

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$: $$ 56786730 \mid mn(m^{60}-n^{60})?$$ Thanks in advance.
1
vote
4answers
30 views

Evaluating the greatest common divisor.

I have a homework question which i'm struggling with, i would be interested in what method i should use to solve the following problems: ...
3
votes
1answer
271 views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers ...
1
vote
1answer
242 views

Is there a simple algorithm I can use for this?

if I were asked to find all integers between 1 and 100 that leave remainder 3 on division by 5 and leave remainder 4 on division by 7, how would I go about this? It seems like such a simple question ...
-1
votes
2answers
106 views

Why is $y^{x-1}-1$ divisible by $x$?

I wanted to know if there is a way to prove that $y^{x-1}-1$ is divisible by $x$. Where $x$ is a prime number and is not equal to $y$, and $y$ is any positive whole number besides $1$. For example, ...
0
votes
2answers
35 views

A formula for a sequence which has three odds and then three evens, alternately

We know that triangular numbers are 1, 3, 6, 10, 15, 21, 28, 36... where we have alternate two odd and two even numbers. This sequence has a simple formula $a_n=n(n+1)/2$. What would be an example ...
1
vote
2answers
52 views

Is it true that for any natural number $p$, if $p$ divides $ab$, then it divides either $a$ or $b$?

I need someone to check my answer. True or False ? For any natural numbers $p$, if $p$ divides the product $a.b$ of two natural numbers $a$,$b$ in $\mathbb{N}$, then either $p$ divides $a$ or $b$. ...
3
votes
0answers
77 views

Prove the equality

Given $a,b,c,d$ are positive integers such that $a^2+b^2+c^2+d^2-ab-bc-cd-da$ is divisible by $abcd$. Prove that $a=b=c=d$.
1
vote
2answers
75 views

How many possible combinations are there of these 4 numbers to add to multiples of 4?

If I have the numbers 0 1 2 and 3, how many combinations of any size but maximum of 4 add to a multiple of 4? EG: 0000 = 0 ( so 0*4), 1111 = 4, 0000 = 0 ( so 0*4), 0112 How many combinations ...
3
votes
2answers
102 views

Making a $m*n$ chocolate bar out of $1*k$ chocolate bars

So I've been puzzled by this problem for some time now: Suppose we have a chocolate bar with dimensions $m*n$ and it is made up out of finite number of $1*k$ chocolates. Proof that for any natural ...
4
votes
1answer
269 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
3
votes
4answers
64 views

Proving that (4-2/1)(4-2/2)…(4-2/n) in an integer.

We have to prove that $(4-2/1)(4-2/2)...(4-2/n)$ is an integer for $n\in\mathbb{N}$. Can we do this by induction? We prove for $n = 1$, which is trivial as $(4-2/1) = 2$ which is clearly an integer. ...
2
votes
2answers
42 views

Coprime Integers Proof Check

$\gcd(a,b)=1$ if and only if there is no prime $p$ such that $p|a$ and $p|b$ Prove it. So I went about doing it through contradiction: If $p|a$ and $p|b$ then $p|(x_{1})(x_{2})(x_{3})...$ where ...
1
vote
4answers
42 views

How to prove that for all positive integers $a,b$, if $a|b$ , then $\gcd(a,b) = a$?

I don't believe there are any counter examples that can be used for this (I think it is true). Could someone help me prove it? I understand why it's true (if I was right about that), but the proof ...
0
votes
3answers
40 views

How to make every integer out of $5k + 8q$?

Expression given: $N = 5k + 8q$ ($k$ , $q$ integer). Prove that we can make any integer from this expression. For example: $0= 5\cdot0+8\cdot0$; $5 = 5\cdot1+8\cdot0$; $3 = 8\cdot1 +5 ...
2
votes
1answer
74 views

The factors of $5^n-3^n-2^n$

I have been assigned the following question. Let $f(n):= 5^n-3^n-2^n$. Prove that (a) $p$ divides $f(p)$ for each prime $p$; (b) $p^{k+1}$ divides $f(n)$ for $n=p^k$, with $p=2,3,5$ and ...
2
votes
3answers
91 views

Divisor in $\mathbb{C}[X]$ $\implies$ divisor in $\mathbb{R}[X]$?

let $P \in \mathbb{R}[X]$ be a real polynomial divisible by a polynomial $Q \in \mathbb{R}[X]$ in $\mathbb{C}[X]$. How can I easily show that $P$ is also divisible by $Q$ in $\mathbb{R}[X]$? A simple ...
3
votes
7answers
356 views

Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$

Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$ I can not understand how to prove it. Please help me.
-1
votes
2answers
25 views

Multiplicity of roots in finite fields of order prime. [closed]

I am having trouble with completing this question from last years exam (part a and d) Let p be a prime, and $f = x^5-1 = (X-1)(X^4+X^3+X^2+X+1) \in \mathbb{F}_p[X]$ Show: (a) if $p\neq 5$ then every ...
3
votes
2answers
56 views

Induction on GCD problem [duplicate]

This is a two part question Given $\gcd(a,b) = 1$ consider $$\gcd \left( \frac{a^n - b^n }{a-b}, a- b\right) $$ It appears that the value of this is always equal to $n$ or $1$. How to prove it? ...
1
vote
3answers
129 views

The number $n^4 + 4$ is never prime for $n>1$

I am taking a basic algebra course, and one of the proposed problems asks to prove that $n^4 + 4$ is never a prime number for $n>1$. I am able to prove it in some particular cases, but I am not ...
3
votes
3answers
198 views

Proving that $\gcd(n!,\ n+1)=1$ or $n+1$

For any positive integer $n$ I need to prove that $\gcd(n!,\ n+1)=1$ or $n+1$ (except one integer). I need to prove both cases and for which $n$ exactly it exists. I tried to use many gcd properties ...
1
vote
0answers
34 views

A Question Related to Zsigmondy's Theorem

I am wondering if there is a way to prove the following statement, which bears some resemblance to Zsigmondy's Theorem. I am not sure if the statement is true, but it seems as though it should be. ...
1
vote
2answers
343 views

Show that the gcd of an odd integer and an even integer is odd

I am using the definition of odd and even integers along with bezout's theorem and I end up with something of the form $d=(2k)m+(2l+1)p$ where $a=2k$ and $b=2l+1$. I've tried to use contradiction as ...