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

If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$.

If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$. So far I have shown that, if $gcd(a,n)=1$, then $gcd(a^j,n)=1$. I also have a ...
1
vote
2answers
95 views

How do you make the coefficients of the simple linear combination of the gcd positive?

I was trying to convert a simple linear combination (and gcd): $$gcd(a,b) = ax + by$$ To have positive coefficients. I did read the following here but didn't really understand it and was looking ...
7
votes
2answers
107 views

$\gcd(a,b)$ compared to $\gcd(3a,b)$

$\gcd(a,b)=\gcd(3a,b)$? They are obviously not equal in general, as $\gcd(ax, bx)=|x|\gcd(a,b)$.
0
votes
0answers
31 views

Linear polynomials relatively prime iff $ad-bc \ne 0$

Two nonzero polynomials $a+bx$ and $c+dx$ are relatively prime in $\mathbb{R}[x]$ if any only if $ad-bc \ne 0$. It's not too hard to show this on a case-by-case basis by enumerating each possible ...
0
votes
4answers
51 views

Prove that $2|(x^4-3) <=> 4|(x^2+3)$

Prove that $2|(x^4-3) <=> 4|(x^2+3)$ What i have right now is: Consider the case (=>): Since $x^4-3$ divides $2$ then, there must exist n belongs to integer, such that $n = \frac{x^4-3}{2}$ I ...
0
votes
2answers
24 views

Stuck with divisibility test in Permutations

How many 5 digit numbers can be formed using digits 0 to 7, divisible by 4, if no digit occurs more than once in a number. 1480 780 1360 1240 None Of These I could calculate the ...
1
vote
1answer
44 views

$x \rightarrow x^n$ is a group automorphism of a finite abelian group G [closed]

How do we prove that the map $\phi:G \rightarrow G$ defined by $\phi(x) = x^n$ for some $n \geq 0$ is a group automorphism of $G$ if $\gcd(|G|,n)=1$?
0
votes
3answers
61 views

If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem: If $a, b, c \in ...
1
vote
4answers
75 views

Prove if $2\mid(x^2-1) $, then $4\mid(x^2-1)$

I have no idea where to start. Any hint(s) or suggestions? Prove if $2\mid(x^2-1) $, then $4\mid(x^2-1)$
0
votes
2answers
27 views

Proof of $g^a \equiv 1 \pmod{m}$ and $g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}$

I am trying to understand the following: $$g^a \equiv 1 \pmod m \quad \text{and} \quad g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}.$$ I have tried a few approaches, ...
4
votes
1answer
47 views

Is it true that the gcd of cubes is the cube of gcd?

Is it true that $\forall a,b\in \mathbb{Z}$, $\gcd(a^3, b^3)=\gcd(a,b)^3$? I cannot find a counterexample, nor have I been able to finish a proof. One thing I tried was: $\gcd(a^3, b^3)= \gcd(a^3, ...
0
votes
2answers
38 views

Divisors of numbers of the form $a^2+2b^2$ with $\gcd(a,b)=1$

Let's say I have a number $n$ which can be written as $a^2+2b^2$ for integers $a,b$. By Fermat/Euler/etc., I know that the primes dividing the squarefree kernel of $n$ cannot be congruent to $5$ or ...
0
votes
1answer
36 views

Formula for the floor of $n/2$, to be proved by induction

How do you compute this when the base case is all wrong?
0
votes
3answers
36 views

What is wrong with my algorithm for finding how many positive integers are divisible by a number d in range [x,y]?

I have been solving basic counting problems from Kenneth Rosen's Discrete Mathematics textbook (6th edition). These come from section 5-1 (the basics of counting), pages 344 - 347. This question ...
1
vote
1answer
42 views

Solving for a variable in an integer divisibility problem

Say I have a problem of the form Where , , and are known integers, is some unknown variable, and is an integer output. Is there an approach I could take to determine if there is some integer ...
4
votes
4answers
524 views

How many integers in the range [1,999] are divisible by exactly 1 of 7 and 11?

This is a question in Kenneth Rosen's Discrete Mathematics textbook 6th edition. I haven't had trouble with any other counting problems regarding "how many numbers in range [x,y] have divisibility ...
1
vote
1answer
29 views

GCD between a polynomial with terms of even degree and a polynomial with terms of odd degree.

We are given a polynomial $p(z)=a_0z^n+b_0z^{n-1}+a_1z^{n-2}+b_1z^{n-3}+\dots=P_1(z)+P_2(z)$, where $P_1(z)=a_0z^n+a_1z^{n-2}+\dots$, $P_2(z)=b_0z^{n-1}+b_1z^{n-3}+\dots$. Let ...
-1
votes
1answer
37 views

Each set of $n$ integers contains at least two items $x,y$ such that $n-1\mid x-y$ [closed]

Can we determine for which $n\in\mathbb{N}$ the statement in the title is true?
0
votes
0answers
10 views

determining no of divisor of quotient '$Q$'

i want to determine number of '$k$'($1 \leq k \leq n$) such that if i divide '$n$' with 'k' then quotient is '$Q$'. for example: $n=5$ and $Q=2$ then ans$=1$ because for only $k=2$ ,$ \frac{n}{k}=Q$. ...
0
votes
0answers
16 views

Problems on Divisability

Consider the following problem If $k-1$ divides $n-1$, $k(k-1)$ divides $n(n-1)$, $n = r$ mod $k$ Find the smallest value m>n such that $k-1$ divides $m-1$ and $k$ divides $m$
0
votes
0answers
37 views

Divisibility: if a|b and b|c, then a|(b+c)

So I'm unsure as to how to prove this: if $a|b$ and $b|c$, then $a|(b+c)$ I'm aware of the divisibility properties such as if $a|b$ then $b=ak$ for some integer $k$. I also know the Transitivity of ...
2
votes
4answers
54 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
26 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
90 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
150 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
19 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
35 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
52 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
46 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
396 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
63 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
21 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 ...
7
votes
1answer
214 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
60 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
24 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$?
3
votes
1answer
53 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
70 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
66 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
51 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
142 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
50 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 ...