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)

2
votes
4answers
42 views

If $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$

I came across this problem in my number theory text and am having a bit of trouble with it: Prove if $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$. Here's what I have so far: If $c\mid ab$, then ...
2
votes
2answers
25 views

Question about G.C.D.

Let, $$a_{n}=n^2+20$$ $$d_{n}=\gcd(a_{n},a_{n+1})$$ where $n$ is a positive integer. Find the set of all values attained by $d_{n}$ I tried, $d_{n}=\gcd(n^2+2n+21,n^2+20)$ ...
5
votes
1answer
86 views

If $a^n-1$ is divisible by $b^n-1$ for all $n$, then $a$ is a power of $b$

Let $a,b$ be natural numbers not equal to $1$ such that $\frac{a^n-1}{b^n-1}$ is natural for any natural $n$. Prove that $a=b^m$ for some natural $m$.
2
votes
2answers
149 views

A question on gcd :

Here's the question: Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that $$ar + bs =1.$$ Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$. I was stuck ...
0
votes
1answer
53 views

Determine all the integer solutions to $23x + 39y = 2$

I would like to calculate all the solutions to this equation using Euclides' algorithm and linear combination after finding the GCD. I suppose it's easy, but I'm a beginner. $23x + 39y = 2$
0
votes
1answer
18 views

Simple problem of divisibility.

Given a number N, N <= 10 ^ 10 and given a integer d, also we are given an integer R we have to find integer L such that for every integer i from L to R the integer division (N / i) = d it is ...
0
votes
2answers
79 views

Prove that $6! \mid n(n+1)…(n+5)$ [closed]

Prove that for all $n \in \mathbb{Z}$, $6! \mid n\cdot(n+1)\cdots(n+5)$ using only criteria of divisibility (without using combinatorial arguments).
2
votes
0answers
34 views

Is there a cycle for modulo operation on a floor?

I have a floor $${\left\lfloor\frac{n}{i}\right\rfloor},$$ where i varies from 1 to n (n can be upto $10^{10}$), and there's another number given 'm' (m upto $10^{5}$). Does ...
0
votes
2answers
50 views

How many 4-digit numbers with $3$, $4$, $6$ and $7$ are divisible by $44$?

Consider all four-digit numbers where each of the digits $3$, $4$, $6$ and $7$ occurs exactly once. How many of these numbers are divisible by $44$? My attack: There are $24$ possible four ...
2
votes
3answers
45 views

How do I prove that numbers not divisible by 3 can be represented as 3x+1 or 3x-1?

I saw that some proofs used the fact that numbers not divisible by $3$ can be represented as $3x+1$ or $3x-1$. But how do I prove that it is true?
0
votes
1answer
44 views

If $n$ is a composite number, then $(7^n-1)/6$ is also composite

Let $n \ge 2$ and $a_n = \dfrac{7^n−1}{6}$. Prove that if $n$ is composite then $a_n$ is composite. I would normally prove something like this with induction but in this case I don't know how to ...
3
votes
3answers
380 views

Divisible by 19 Induction Proof

Prove by induction that for all natural numbers $n$, $\frac{5}{4}8^n + 3^{3n-1}$ is divisible by $19$. I'm running into trouble at the inductive part of the step, I am currently attempting to ...
1
vote
5answers
46 views

Not clear on what we mean with numbers with infinite digits

I am confused on a rather simplistic question. 1/3 = 0.333333333333 to infinity. So it has infinite digits. How is it possible to multiply such a number with another one and get a finite number? 6/3 = ...
3
votes
1answer
59 views

Greatest common divisor problem involving $a^p+b^p$ [closed]

Let $\gcd(a,b)=1$ for some $a,b\ \epsilon \ \mathbb{N}$. Prove that for any odd prime p: $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1,~~~~ \text{or} ~~~p.$$
0
votes
0answers
20 views

Could you give a definition of what is a superior highly composite number using only words?

I know very well what is a superior highly composite number, but I would like to see how could we (roughly) define what is a superior highly composite number using only words (using no equations and ...
6
votes
1answer
162 views

Seeking help extending Vieta-jumping to higher powers

I am trying to prove the following conjecture. Conjecture. If $r > s \ge 1$ are relatively prime integers such that \begin{equation} (r-s)^4-1 \equiv 0\!\pmod{4r^2s}, \tag{1} \end{equation} ...
2
votes
4answers
52 views

system of congruence - my approach

We have: $$k^3 + l^3 \equiv 0 \pmod{17}\\ k^2 + l^2 \equiv 0 \pmod{17} $$ And I get: $$k = 17n+r_k\\ l = 17m+r_l$$ And I analyzed possible rests respect to system of congruences. My result is: $$ ...
1
vote
5answers
59 views

If $p^2\,$is divisible by 3, why is p also divisible by 3? [duplicate]

I came across this in proving that the $\sqrt{3}$ is irrational
0
votes
2answers
24 views

Is this a valid proof technique regarding the divisibility of numbers?

Claim: All numbers of this sequence are relatively prime to one another: $$2^1 + 1, 2^2 + 1, 2^4 + 1, \ldots, 2^{2^n} + 1$$ So, I decided to include $2^0 + 1$. That way: Base case: $$2^0 + 1 ...
0
votes
1answer
23 views

number system and divisibility

could anyone please find a solution to that problem: $b$,$c$,$d$ are consecutive even integers such that $2\lt b \lt c \lt d$. what is the largest positive integer that MUST be a divisor of $bcd$?
2
votes
1answer
44 views

Determine the divisibility of a given number without performing full division

My question is slightly more complicated than what's implied on the title, so I will start with an example. Given any number $N$ on base $10$, we can easily determine whether or not $N$ is divisible ...
2
votes
0answers
18 views

How to know if the number of divisors in a determined range for a number is odd or even [duplicate]

I would like to know if the number of divisors for the number in a determined range is odd or even without counting the divisors, I think the question is a little tad fuzzy, thus, I will supply the ...
4
votes
1answer
69 views

Factors of integers of the form $2^n-1$

I came across a problem where i had to tell the number of divisors of $2^i-1$ which are of the form $2^j-1$. I saw many contestants using the fact that if $i$ is divisible by $j$ then $2^i-1$ is ...
2
votes
0answers
59 views

How to find the approximate basic frequency or GCD of a list of numbers?

I could't actually summarize the question in the title, so I'll explain my situation. I want to tell the integer numbers which act as the best approximate basic frequencies of a list of real numbers: ...
0
votes
2answers
75 views

Prove that if $p$ is prime, and $a^2=b^3$

I have an exercise that I don't know how to solve. I tried to solve it in many ways, but I didn't get any progress in proving or disproving this... The exercise is: Prove or disprove: if $p$ is a ...
1
vote
1answer
50 views

Binomial Congruence (mod 5) Identity

I've got a (hard?) Putnam-style problem that I've been given to look at . . . I've never worked any problem even vaguely like this, but my director thinks I should be able to do it. I doubt it (100% ...
4
votes
1answer
127 views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
10
votes
3answers
2k 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
49 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 ...
2
votes
0answers
18 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 ...
1
vote
1answer
48 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?
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
87 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
239 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
85 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
101 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
41 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
54 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 ...
9
votes
1answer
102 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 ...
4
votes
1answer
58 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, ...
3
votes
2answers
100 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 ...
1
vote
1answer
27 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
29 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
41 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
39 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 ...
1
vote
1answer
244 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 ...
5
votes
3answers
95 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?
3
votes
1answer
286 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 ...
3
votes
0answers
79 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
4answers
32 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: ...