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)

0
votes
2answers
282 views

Long division: 24158 divided 6

Long division has always been a weakness of mine and some how I've gotten through school and sixth form without it, but i'd like to learn it, it's just that I have a problem with intuition. So I know ...
6
votes
2answers
53 views

The product of all differences of the possible couples of six given positive integers is divisible by 960.

How can I show that the the product of all differences of the possible couples of six given positive integers is divisible by $960$? $$x_1≥x_2≥x_3≥x_4≥x_5≥x_6$$ $$960\mid (x_1-x_2 )(x_1-x_3 ...
0
votes
1answer
34 views

Suppose $m,n$ are positive integers such that $a-b|a^m-b^n , \forall a,b \in \mathbb Z , a-b \ne0$ , then is it true that $m=n$?

Suppose $m,n$ are positive integers such that for all $a\neq b$ one has $a-b\mid a^m-b^n$, then is it true that $m=n$ ?
2
votes
1answer
72 views

On Descartes numbers

This question is an offshoot of this earlier MSE post. Citing Banks, et. al.: "Let us call an integer $n$ a Descartes number if $n$ is odd, and if $n = km$ for two integers $k, m > 1$ such that ...
0
votes
0answers
109 views

Automata to detect numbers divisible by $7$

I have a task and I really have no idea how to solve it. Build deterministic finite automata such that it can detect numbers divisible by $7$. So our alphabet is $\left\{0,1,2,3,4,5,6,7,8,9\right\}$ ...
0
votes
0answers
45 views

How does the factor command on the TI-89 works?

So to put my question in context, I am working on the following problem. Let $N=1291233941$. Eve's magic box tells her the following three encryption/decryption pairs for $N$: $$(1103927639, ...
0
votes
2answers
36 views

Prove $n!\mid\prod_{k=i}^{i+n-1}k$

I have no idea how to prove this, I haven't yet learned much about this kind of product. $$ n!\mid\prod_{k=i}^{i+n-1}k $$
0
votes
3answers
41 views

Prove that gcd(e,f)=1

could someone please help me with this proof? Suppose that a, b ∈ N, and d = gcd(a, b). Since d divides a, we have a = de for some integer e, and similarly b = df for some integer f. Prove that ...
2
votes
4answers
67 views

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction What I thought: Inductive hipothesis: $$ 5^{2n}+12n^2-36n-1=24k $$ Inductive step: $$ 5^{2(n+1)}+12(n+1)^2-36(n+1)-1=24q $$ $k,q \in \mathbb{Z}$ ...
1
vote
1answer
31 views

divisible large degree polynomial

Let $n$ be an even positive integer and $a$, $b$ real numbers such that $b^n=3a+1$. Prove that if $(X^2+X+1)^n-X^n-a$ is divisible by $X^3+X^2+X+b$, then $a=0$ and $b=1$. I am thinking of using the ...
2
votes
4answers
53 views

Find every n $\in \mathbb{N}$ such that $n+1 \mid n^2+3$

Find every n $\in \mathbb{N}$ such that $n+1 \mid n^2+3$ What I did: $n+1 \mid n^2+3$ and $n+1 \mid (n+1)^2=n^2+2n+1$ So $n+1 \mid (n^2+3)-(n^2+2n+1) \Longrightarrow n+1\mid-2(n+1)$ ...
0
votes
2answers
17 views

Let $n,r,a$ be positive integers with g.c.d.$(a,d)=1$ , does there exist integer $m$ relatively prime to $n$ such that $d|m-a$?

Let $n,r,a$ be positive integers with g.c.d.$(a,d)=1$ . Does there exist integer $m$ such that $d|m-a$ and g.c.d.$(m,n)=1$ ?
4
votes
2answers
78 views

To Find $a$ such that $2^{1990} \equiv a\pmod {1990}$. [duplicate]

To Find $a$ such that $2^{1990} \equiv a\pmod {1990}$. $1990 = 2 \times 5 \times 199$. Now $a \equiv 0 \pmod {2}$, $a \equiv 4 \pmod{5}$ and $a \equiv 29 \pmod{199}$. Taking first two together we ...
1
vote
1answer
71 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
23
votes
6answers
13k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
2
votes
3answers
310 views

“Quadly” numbers with just 4 factors

A positive integer with exactly four positive factors is called "quadly". Compute the least $n$ for which each of $n,n+1$ and $n+2$ is quadly. (ARML 2008) My method of attacking this problem started ...
0
votes
3answers
53 views

Working out a reverse formula

My math skills are getting rusty. I am trying to work out what the formula should be for calculating price, $P$, based on a formula I used to calculate margin, $\mu$, with a parameter, cost, $C$. ...
9
votes
2answers
83 views

$5^{th}$ power of any integer is of the form $11k$ or $11k +1$ or $11k -1$.

$5^{th}$ power of any integer is of the form $11k$ or $11k +1$ or $11k -1$. Let the integer be $x$. If $x$ has a factor $11$ then $x^5$ is of the form $11k$. Now we consider the case where $11 ...
0
votes
4answers
33 views

Is there a quick parity test for integers expressed with odd radicies?

For integers expressed with an odd base, is there an easy way to tell if the number is odd or even? For an even base, if the ones digit is even, so is the integer. But this doesn't hold true for odd ...
0
votes
1answer
28 views

Solving number divisibility problem using cardinal number of sets!

How many natural numbers $n<10^6$ are divisible by $7$ but not with $10,12$ and $25$? Theorem: Let $n,k\in \mathbb{N}$ and $k\leq n$, then in the set $\{1,2,...,n\}$ we have exactly $\left \lfloor ...
2
votes
0answers
86 views

$(z-k)$ is composite then $(z-1)+(k-1)$ is also composite(A proof for composite number).

Given $z(z-1)$ is divisible by all prime $< n$ where $ n>\sqrt z$ $(z+k)$ is prime. Prove or disprove if $(z-k)$ is composite then $(z-1)+(k-1)$ is also composite. ...
0
votes
0answers
57 views

On odd perfects and spoofs

This question is an offshoot of this MSE post. Let $\sigma$ be the classical sum-of-divisors function. An odd perfect number $N$ is said to be given in Eulerian form if $\sigma(N)=2N$ and ...
5
votes
5answers
62 views

Prove that for $n \gt 6$, there is a number $1 \lt k \lt n/2$ that does not divide $n$

My nine year old asked this question at lunch today: Is there a number that is divisible by everything that is half or less than the number? I immediately answered, "No. I mean, 6. But not for any ...
1
vote
5answers
63 views

Is it possible to split a division problem into parts, like in multiplication?

In multiplication we can mentally split a problem that is too big into multiple problems. For example: 26 * 40 = (20 * 40) + (6 * 40) = 800 + 240 = 1040 This is a very quick way to multiply ...
1
vote
1answer
91 views

Using Extended Euclidean Algorithm for $85$ and $45$

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
0answers
23 views

Divisibility of orders on a group

Let $h \in H \leq G$, where $G$ is a finite group and $H$ is a subgroup. From Lagrange's Theorem, we know $o(h)$ divides $|G|$. It is still true for $H$? That is, is $o(h)$ going to divide $|H|$? I ...
0
votes
1answer
42 views

Quotient and Remainder of Numbers

May I ask what is the logic behind the quotient and remainder for numbers in such situation. ...
1
vote
2answers
35 views

Show that if $\gcd(r,s_1) =\gcd(r,s_2) = 1$, then $\gcd(r,s_1s_2) = 1$

Never mind the question. I want to try to solve that on my own. What I want to understand is how this: "Hint. $1 = ar + bs_1,\ 1 = ar + bs_2$" relates to solving it. I'm a little confused by this ...
1
vote
1answer
34 views

For what positive integers is this number-theoretic equation true?

For what odd (positive) integers $x$ is this number-theoretic equation true? $$\gcd(x^2, \sigma(x^2)) = 2x^2 - \sigma(x^2)$$ Here, $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$, and ...
4
votes
5answers
88 views

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$.

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$. I've started by letting $P(n) = n^3+11n$ $P(1)=12$ (divisible by 6, so $P(1)$ is true.) Assume $P(k)=k^3+11k$ ...
1
vote
2answers
27 views

Proving divisibility of $a^3 - a$ by $6$

As part of a larger proof, I need to show why $a^3-a$ is always divisible by $6$. I'm having trouble getting started.
2
votes
2answers
69 views

Find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm.

I need to find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm. Wolfram shows that the gcd is equal to $1$, but for some reason I don't get the same answer. ...
-5
votes
1answer
65 views

Division by zero after removing factor. [duplicate]

I know that anything divided by zero is undefined and I understand why. However, I have just discovered this sum, and it confused me greatly. Could anyone explain what is going on here: $$x-x=0$$ ...
1
vote
3answers
31 views

If $x,y$ are integers greater than $1$ and $n$ is a positive integer such that $2^n + 1=xy$ , $\exists 1< a<n$ such that $2^a|x-1$ or $2^a|y-1$?

If $x,y$ are integers greater than $1$ and $n$ is a positive integer such that $2^n + 1=xy$ , then is it true that either $2^n|x-1$ or $2^n|y-1$ ? I have only been able to observe that both $x,y$ are ...
0
votes
1answer
31 views

Simple number theory

I'm new in number theory and I was asked this question: For the number $N$ output the amount of numbers $M$, such that $1 \le M \le N$, $\gcd(M, N) \ne 1$ and $\gcd(M, N) \ne M$. How can i solve it?
2
votes
2answers
85 views

Divisibility of sum of two numbers by $24$.

Let $m$ and $n$ be natural numbers such that $(mn + 1)$ is divisible by $24$. Then $m + n$ is divisible by: $2$ $3$ $8$ $12$ $24$ All of the above The answer given is 6. (all of the above). ...
0
votes
1answer
44 views

Show that if $p\mid m^2$ then $p \mid m$ and hence $p^2 \mid m^2$

Show that if $p\mid m^2$ then $p \mid m$ and hence $p^2 \mid m^2$ I don't understand what is being asked of me. I thought this question was asking if $p$ divides $m^2$, then $p$ divides $m$, and ...
0
votes
1answer
34 views

Polynomial long division modulo 7,

I need to determine the quotient and remainder using polynomial long division in $Z_7[x]$. I'm not sure how to tackle it with the polynomials given, and I'm growing frustrated by it. I need to divide ...
3
votes
1answer
81 views

Values of $\gcd(a-b,\frac{a^p-b^p}{a-b} )$

I don't know how to prove the following result. Let $p$ be a prime number and let $a,b \in \mathbb Z$ such that $\gcd(a,b)=1$ Then $\gcd (a-b,\frac{a^p-b^p}{a-b}) = 1 $ or $ p $ (gcd should be ...
1
vote
2answers
55 views

Prove that 100…500…1 (100 zeros in each group) is not a perfect cube?

How can i prove that 100...500...1 [100 zeros in each group ( ... is 100 zeros)]is not a perfect cube? I tried symmetric features of the number but could not figure out anything related.any ideas ...
4
votes
1answer
44 views

Prove that $2^{4n}+1$ cannot be a prime if $3|n$

$2^{4n}+1$ cannot be a prime if $3|n$ and $n>0$ My Try: $$2^{12k}+1\equiv (-1)^{3k}+1 \equiv0\pmod{17}$$ So it divisible by $17$ for odd $k$. But how to complete the proof?
13
votes
4answers
1k views

Is there a sequence of 5 consecutive positive integers such that none are square free?

Is there a sequence of 5 consecutive positive integers such that none are square free? A number is square free if there is no prime number p such that $p^2 \mid n$ What I've tried doing so far is to ...
2
votes
4answers
53 views

Proving that if $8\mid (n^2+2n)$ then $2\mid n$

Let $n\in \mathbb N$ prove that if $8\mid (n^2+2n)$ then $2\mid n$. From the given, there exists $k\in \mathbb N$ such that $8k= (n^2+2n)$, take $k=1$, and we get $2\cdot 4 = n(n+2)$. Now my ...
2
votes
1answer
40 views

Prove that $[(a|b)\land(c|d)]\Longrightarrow ac|bd;\, a|b\Longrightarrow ac|bc;\, ac|bc\Longrightarrow a|b.$

Prove that: $$(a): [(a|b)\land(c|d)]\Longrightarrow ac|bd;$$ $$(b): a|b\Longrightarrow ac|bc;$$ $$(c): ac|bc\Longrightarrow a|b.$$ Proof: (a) By definition of divisibility, ...
8
votes
4answers
121 views

Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.

I'm not sure if it's correct, but what I have so far is; $$21n^5 + 10n^3 + 14n ≡ (1 + 0 - 1) ≡ 0 \mod 5$$ but I'm having trouble solving it in $\bmod 3$. I have: $$21n^5 + 10n^3 + 14n ≡ (0 + (?) + ...
0
votes
3answers
154 views

The largest number that will perfectly divide $101^{100}–1$ [closed]

The largest number amongst the following that will perfectly divide $101^{100}–1$ is: A. $100$ B. $10,000$ C. $100^{100}$ D. $100,000$ Can someone please answer this question. Thanks in advance.
0
votes
1answer
27 views

Trivial and nontrivial GCD of polynomials

What is the difference between trivial and non-trivial GCDs of two polynomials: $f,g$ where $f,g \in Q[x]$? I know if $f,g \in Z[x]$, the only non-trivial GCD is 1, and everything else is trivial. ...
0
votes
1answer
46 views

Is there a way to prove that 2y(y-1) is divisible by four other than by means of induction?

I am going trough some of my older textbooks and in one problem you have to prove that 2y(y-1) is divisible by four if y is a whole number. Its trivial to prove this by using induction, but this ...
3
votes
0answers
49 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
2
votes
1answer
46 views

What does a distributed lattice have to do with GCD and LCM?

$\newcommand{\lcm}{\operatorname{lcm}}$I am lost while following this explanation: Let $$A(g, i) = \gcd(F_{g}, \lcm(F_{a_1}, F_{a_2}, \ldots , F_{a_i}))$$ and $$X = \lcm(F_{a_1}, F_{a_2}, \ldots , ...