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
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
56 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
103 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
59 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
104 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
29 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
32 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
306 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
85 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
33 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
4answers
67 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. ...
-1
votes
2answers
30 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
65 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
votes
2answers
108 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
1answer
37 views

Check my proof : gcd(a,b)=1=gcd(x,y) => (xa,yb)=gcd(x,b) gcd(y,a)

Note: (x,y) means gcd(x,y) I managed to prove the next Proposition: Let $(a,b)=1=(x,y)$. Then $(x a,y b)=(x,b)(y,a)$. It can be easily be generalized for the case that $(a,b)\neq1$ and or ...
0
votes
4answers
94 views

Find a pair of integers $n,x$ such that $84 = nx + (n-1)n$ and $x$ is odd [closed]

I have a equation like this: $$84 = nx + (n-1)n$$ where, $x$ is odd. I need to find the fastest way to find a possible $n$ and $x$. (In this case: $n = 6, x = 9$) Edit: Maybe the background ...
-1
votes
3answers
38 views

Easy question but tough judgement -Are both boundary points included in a time interval as in this question

So the question is - Six bells commence tolling together at intervals of 2,4,6,8,10 and 12 seconds respectively In thirty minutes how many times do they toll together? (A) 16 (B)15 This question is ...
-1
votes
4answers
35 views

If GCD of x and y is G then GCD of x and x+y is also G. but how to prove it? [closed]

If GCD of x and y is G then GCD of x and x+y is also G but how to prove it?
1
vote
0answers
38 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
1answer
28 views

Length of smallest repunits divisible by primes

I want to prove this statement from Wikipedia: It was found very early on that for any prime p greater than 5, the period of the decimal expansion of 1/p is equal to the length of the smallest ...
1
vote
3answers
105 views

Number theory proofs regarding gcd's

How would you prove if $ad-bc = 1$, then $(a+c,b+d)=1$
2
votes
3answers
181 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 ...
0
votes
1answer
49 views

Generalized Fibonacci Sequence

I'm having trouble with a problem I encountered while studying Number Theory. This problem comes from the book Number Theory by George E. Andrews. It defines a generalized Fibonacci sequence $F_1$, ...
2
votes
2answers
123 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
-1
votes
2answers
34 views

Solution for trinomial divided by binomial equation

I have the following equation to solve. I know that the answer is -5, I made several attempts at this, and arrive at a different answer. My first thought was to factor out the trinomial, but that ...
1
vote
3answers
78 views

Prove that $17$ divides $9a + 5b$

So, according to the book, for all $a, b, c$ that are elements of integers, it holds that $a|b$ implies $a|bx$ for all $x$ that is an element of integers. In other words it works for all ARBITRARY $x$ ...
1
vote
3answers
69 views

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

As stated in the title, the problem to prove is Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$. I think I've proved it, but I would like a second opinion. Here ...
1
vote
1answer
41 views

Polynomial and its derivative have a common factor?

When is $gcd(p(x),p'(x))\ne 1$ where $p(x)$ is a polynomial? That is when does the derivative of a polynomial and the polynomial has a common factor? By when i mean some condition for the ...
4
votes
4answers
186 views

Inequalities, when does the sign change here?

I have encountered a problem with inequalities. I have been looking at examples provided by two websites which 'solve' inequalities, however when I try using my own method, the extremely simple ...
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 ...
0
votes
2answers
99 views

Divisibility crieteria

This is a follow-up question. The problem is: Given two natural numbers, $m$ and $n$, and $n \vert m^2$. Find necessary and sufficient conditions for $n \vert m$. Here are what I find: ...
2
votes
2answers
102 views

Ring such that $q^2\mid p^2$ does not imply $q\mid p$?

Let $R$ be a commutative ring with $1$ and suppose $q^2\mid p^2,$ for $p,q \in R$. Unless $R$ is a UFD, I don't believe I can conclude that $q\mid p,$ but I would like to know a concrete ...
1
vote
4answers
53 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
2
votes
0answers
26 views

Prove the congurence

I am looking for a proof of Gauss's generalization of Wilson's Theorem. Let $S$ be the set of all the integers which are less than and mutually prime to $n (>4)$ (not of the form $p^\alpha$, ...
0
votes
1answer
82 views

Divisibility of huge numbers

Please help me to solve my homework ;) Prove that for any positive integer $n$ a square of rather big number divides even more huge number: $${\LARGE \left.\underbrace{33\dots 3}_{1\underbrace{00\dots ...
1
vote
0answers
49 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
0
votes
2answers
33 views

Equation Theory: A polynomial with specific remainders when divided by specific divisors. What is the remainder when divided by BOTH divisors

Again, for my Equation Theory class, I have the subject question.$p(x)$ has a remainder of 3 when divided by $x-1$ and a remainder of 5 when divided by $x-3$. What is the remainder when $p(x)$ is ...
0
votes
1answer
54 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
1
vote
1answer
51 views

Question in elementary number theory

I have a question. Suppose that $a$ and $b$ are two natural numbers so that $ a<b$ and $ a\nmid b$. Put $ d=ka$, where $ k\not=0,1,t\dfrac{b}{\gcd(a,b)}$, for $ t\geq 1$. I want to prove that $ ...
0
votes
5answers
42 views

How do you prove this divisibility?

If $n$ is any natural number, prove that $3\mid 2^{2^n}-1$ is true. I can't find out how to do it. Thanks.
1
vote
1answer
67 views

Characterizing the primes which don't divide any Pell-Lucas number(s)

For integer $n$, let $P_n$ be a Pell number, and $Q_n$ its companion. Is there a characterization of the prime numbers $p$ which don't divide any $Q_n$? By brute-force search, I found that this ...
3
votes
1answer
96 views

Probability that two random integers have only one prime factor in common

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is ...
0
votes
3answers
30 views

Help with understanding definition of divisibility in this case.

I have a proof that shows that if $5 \mid xy$ then $5 \mid x$ or $5 \mid y$. It's pretty clear to me that I can just say that suppose $5 \mid x$, then $x=5a$, where $a$ is an integer. then $xy = ...
3
votes
5answers
658 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
1
vote
0answers
33 views

Find the Conditions

Let $a, b, c, d, r, s \in \mathbb{N}$. Find the necessary and sufficient conditions under which $r \mid (a-b)$ and $s \mid (c-d)$ $\implies$ $\operatorname{lcm}$ $(r,s)\mid(ac-bd)$. A little ...