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
5answers
239 views

Show that if $a^n\mid b^n$, then $a\mid b$.

I have a question from a sample exam I have difficulties to solve: Show that if $a^n\mid b^n$, then $a\mid b$. I don't have any idea how to start. I'd like to get helped. thanks!
0
votes
1answer
68 views

Ruffini's rule, a problem with 3 variables and apparently only 2 conditions

Please help me to solve this problem using Ruffini's rule. Given $P(x) = a x^3 + 2 x^2 + c x + d$, please help me to determine the values of $a$, $c$ and $d$ so that P(x) is divisible by $(3x+2)$ and ...
1
vote
1answer
48 views

Digit Root of $2^{m−1}(2^m−1)$ is $1$ for odd $m$. Why?

The Wiki page on Perfect numbers says: [A]dding the digits of any even perfect number (except $6$), then adding the digits of the resulting number, and repeating this process until a single digit ...
0
votes
4answers
72 views

Divisibility for natural numbers

Prove that $(\forall n \in \Bbb N)(4 \mid 5^n-1 )$ I only know that if $ a \mid b \implies b =a \times q $ with $a,b,q \in \Bbb Z$ So(...) $4\mid5^n-1 \implies 5^n-1 = 4 \times q$ But I can't ...
0
votes
2answers
161 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 ...
2
votes
0answers
80 views

An upper bound on the least common multiple of the first $2n+1$ integers

Let $p$ be a prime number and let $a, n \in \mathbb{N}$. Then $$ p^a \mid \operatorname{lcm}(1, 2, \dots, 2n+1) \implies p^a \leq 2n + 1 \implies a \leq \dfrac{\ln(2n+1)}{\ln p}$$ and ...
3
votes
3answers
212 views

Demonstração do Teorema de Bezout. (Proof of Bézout's Theorem)

Gostaria de saber como provar usando divisibilidade o teorema de Bezout $(a,b)=d\Longrightarrow \exists f,g\in\mathbb{Z^*}$ tal que $af+gb=d$ I'd like to know how to, using divisibility, ...
4
votes
2answers
135 views

Proving $\gcd( m,n)$=1 [duplicate]

If $a$ and $b$ are co prime and $n$ is a prime, show that: $\frac{a^n+b^n}{a+b}$ and $a+b$ have no common factor unless $a+b$ is a multiple of $n$ Also enlighten me why $n$ has to be prime so that ...
3
votes
3answers
211 views

Show that $ (n+1)(n+2)\cdots(2n)$ is divisible by $ 2^n$, but not by $ 2^{n+1}$

I have no idea how to prove this. Can anyone help me through the proof. Thanks.
0
votes
1answer
48 views

If $AB \in \mathbb{N}$ and $B \in \mathbb{N}$, does it follow that $A \in \mathbb{N}$?

I am a bit confused myself, so I apologize if the answer to this particular question is trivial: If $AB \in \mathbb{N}$ and $B \in \mathbb{N}$, does it follow that $A \in \mathbb{N}$? Here, ...
1
vote
1answer
60 views

divisibility of integral part of a surd

Given that "$n$" belongs to prime numbers and is greater than 2 ; $(a,b)$ belongs to integers and $0<\sqrt{a}-b<1$ $(\sqrt{a}+b)^n=N+f$ where $f \in (0,1)$ Show that $N$-$2b^n$ is ...
5
votes
4answers
476 views

Divisibility by 7

What is the fastest known way for testing divisibility by 7? Of course I can write the decimal expansion of a number and calculate it modulo 7, but that doesn't give a nice pattern to memorize because ...
0
votes
0answers
82 views

Fibonacci sequense, problem od division

How to show that $7\mid F_m\Longrightarrow 8\mid m$ and $4\mid F_m\Longrightarrow 6\mid m$, knowing that (I) Two consecutive terms in the Fibonacci sequence are relatively prime. (II) In ...
5
votes
3answers
366 views

Prove that $2^n3^{2n}-1$ is always divisible by 17

Prove that $2^n3^{2n} -1$ is always divisible by $17$. I am very new to proofs and i was considering using proof by induction but I am not sure how to. I know you have to start by verifying the ...
0
votes
1answer
135 views

Find number of divisors upto $10^9$

I am new to number theory, I have to find the number of divisors up to $10^9$, but i dont know how to do it efficiently and store it in an array in 'c'. I am using sieve algo to find the number of ...
2
votes
2answers
54 views

Divisibility implications proof

I would like some help setting up the proof for this. It's a simple enough idea, but I struggle with proofs for these the most, because it just seems so obvious to me. Prove: if $a$, $b_1$, $b_2$ ...
6
votes
1answer
715 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
3
votes
1answer
458 views

Find Divisor and Dividend from Remainder

I am developing some software to "Mutate" inline constants in source code to make them hard to read (eg. Obfuscation) and need a way to determine two values that when divided by each other gets a ...
3
votes
2answers
80 views

Arithmetical proof of $\cfrac{1}{a+b}\binom{a+b}{a}$ is an integer when $(a,b)=1$

When $(a,b)=1$, $\cfrac{1}{a+b}\binom{a+b}{a}$ refers to the number of paths from one corner to its opposite corner of an $a\times b$ lattice that lies completely above (or below) the diagonal. ...
2
votes
3answers
148 views

Solve congruence equation $3373x \equiv 2^{485} \pmod{168}$

$$3373x \equiv 2^{485} \pmod{168}$$ Uhm...I don't even know how to start. $GCD(3373,168)=1$, so solution exists. Usually I would use extended Euclidean algorithm and get the outcome, but it would ...
0
votes
3answers
438 views

if $X^2 +AX+B=0$ has a rational root, prove it is an integer. [duplicate]

If $x^2 + Ax +B =0$ has a rational root, prove it is an integer. I don't even know where to start on this problem. I've had it on my white board for about a week and keep looking at it, but can't see ...
0
votes
2answers
1k views

How do I prove $\gcd(a,b) = \gcd(a+b, b)$ [duplicate]

How do I prove $\gcd(a, b) = \gcd(a+b, b)$. I know that by the euclidean algorithm, I can obtain the following equations $ax_1 + by_1 = \gcd(a, b)\tag{1}$ $(a+b)(x_2) + (b)(y_2) = \gcd(a+b, ...
9
votes
4answers
419 views

Middle school number theory

Find at least three numbers that satisfy all three conditions: (1) there is a remainder of $1$ when the number is divided by $2$; (2) there is a remainder of $2$ when the number is divided by $3$; ...
0
votes
2answers
123 views

Prove the following divisibility statements without use of induction

(a) $5$ $|$ $3^{3n+1}+2^{n+1}$ (b) $21$ $|$ $4^{n+1} + 5^{2n-1}$ (c) $24$ $|$ $2 \cdot7^n + 3 \cdot5^n - 5$ These are trivial by using induction. But I have tried to prove it by binomial theorem and ...
1
vote
2answers
150 views

Division algorithm: What is the meaning of the propositions?

I face trouble with understanding certain propositions in the division algorithm. For example, Let $a,b \in \Bbb Z, b>0$. Let $S = \{a - qb: q \in \Bbb Z, a - qb \geq 0\}$. To ...
4
votes
1answer
86 views

Simplifying difficult congruence equations

$$2842x \equiv 1547 \pmod{103} $$ How can I simplify this? $GCD(2842,103)=1$, so my guess would be to divide the equation by 7, which is the $GCD$ of 2842 and 1547. So: $$406x \equiv 221 ...
2
votes
1answer
124 views

Solve the congruence using fast exponentiation algorithm to find an inverse?

$$24x \equiv 17 \pmod{217}$$ I got this excercise from some book, the question is - solve the congruence, using fast exponentiation algorithm to find an inverse...Hmm, do you see some inverse here to ...
1
vote
1answer
73 views

A problem about divisibility: Partition a number into two and three digits

Now I have proved the following two problems: (1) Prove that a number and the sum of its digits have the same remainder upon division by 9. (2) Given an interger, consider the difference ...
0
votes
1answer
53 views

Prove that all practical numbers not of the form $2^n$ are pseudoperfect

Prove that all practical numbers not of the form $2^n$ are pseudoperfect. practical - $n$ such that every smaller integer is expressible as a sum of distinct divisors of $n$ pseudoperfect - $n$ such ...
2
votes
3answers
83 views

Prove that for all odd $n$, there is an $m$ such that $2^m - 1$ is divisible by $n$

I've been trying to solve a problem that reads as such Prove that for all odd positive integers $n$, there exists a positive integer $m$ such that $(2^m) - 1$ is divisible by $n$. Proof by ...
0
votes
1answer
114 views

Dividing the linear congruence equations

$$42x \equiv 12 (mod 90)$$ This is pretty simple congruence equation. $GCD(42,90)=6$; $6|12 =>$ solutions exist. I've always been solving congruence equations with that scheme: ...
2
votes
1answer
125 views

Solving system of linear congruence equations

$$23d \equiv 1 \pmod{40}$$ $$73d \equiv 1 \pmod{102}$$ How can I solve this? 40 and 102 are not coprime, so I figured I can factor the moduli: $$23d \equiv 25 \pmod 8$$ $$23d \equiv 26 \pmod 5$$ ...
0
votes
1answer
131 views

what is the pattern in the distribution of divisors.

I made a table that shows the number of divisors for each number less than 500, and i think that there is a pattern, for example when there is a spike in the number of divisors the surrounding numbers ...
2
votes
1answer
88 views

This correct this demonstration of Number theory (binomial Expressions)

$$\\$$Em minha apostila tem as demonstrações dos seguintes lemas:$$\text{Lema (*): Sejam $a,m,n,q,r\in\mathbb{N}$ com $a\geq2$ tais que $m=nq+r$ then:}\\(a^m-1,a^n+1)=\begin{cases}(a^n+1,a^r-1)& ...
1
vote
1answer
101 views

Divisibility of multinomial by a prime number

What is the condition for divisibility of multinomial $ \dbinom {n}{x_1, x_2, \dots, x_k} $ by a prime $p$? Update: I tried to solve using a generalisation of Lucas Theorem by representing the $n$ ...
0
votes
2answers
1k views

How to find modular multiplicative inverse

For example: $$63x \equiv 1 (mod 17)$$ I wanna find the multiplicative inverse here so that I can use this in the Chinese reminder theorem. Example: $$x \equiv 2 (mod 3)$$ $$x \equiv 4 (mod 5)$$ ...
1
vote
4answers
260 views

Divisibility and the Fibonacci sequence

While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it. Show that if the Fibonacci sequence has a term divisible by a natural number ...
0
votes
1answer
93 views

Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
0
votes
2answers
47 views

Solving system of congruences using CRT

$$4x \equiv 5 \pmod 7$$ $$7x \equiv 4 \pmod {15}$$ I need to solve this system of congruences using Chinese Reminder Theorem. It would be easy to use CRT if not those 4 and 7 near the x variables. ...
1
vote
1answer
54 views

$17\mid19^{8n}-1\;\;\forall n\in\mathbb{N}$?

Show that $17\mid19^{8n}-1\;\;\forall n\in\mathbb{N}$. I thought about using arithmetic of the remains, proving that $1\equiv19^{8n}\pmod{17}$ And I could not do it: (
0
votes
2answers
116 views
0
votes
0answers
40 views

Chinese reminder theorem - evaluating inverses

So, this is the CRT scheme I know: $$x=b_{1}*N_{1}*a_{1} + b_{2}*N_{2}*a_{2} + ...$$ Where $a_{x}$ is: $N_{x}a_{x} \equiv 1 (mod $ $n_{x})$ All right, so let's assume I have the following system ...
4
votes
2answers
77 views

Solving $x \equiv 9 \pmod{11}, x \equiv 6 \pmod{13}, x \equiv 6 \pmod{12}, x \equiv 9 \pmod{15}$

$$x \equiv 9 \pmod{11}$$ $$x \equiv 6 \pmod{13}$$ $$x \equiv 6 \pmod{12}$$ $$x \equiv 9 \pmod{15}$$ Does this system have a solution? I want to solve this using the Chinese remainder theorem, but ...
1
vote
2answers
363 views

Why should we append zeros during CRC calculation?

Say we have M as message bits , why do we need to append r-zeros to M message bits before performing the division to obtain r-bit checksum. Why don't we directly perform the division on the M message ...
2
votes
3answers
100 views

Show that $19\mid 12^{2013}+7^{2013}$ [duplicate]

Show that $$19\mid 12^{2013}+7^{2013}$$$$$$No use of modular arithmetic, have not come this content.
1
vote
1answer
78 views

Divisibility of Multivariate Polynomials with Common Roots

Let $f(x_1,...,x_n)$ and $g(x_1,...,x_n)$ be polynomials in $\mathbb{C}[x_1,...,x_n]$ such that all roots of $f$ are roots of $g$ as well (but not necessarily viceversa). The question is: Does $f$ ...
0
votes
2answers
389 views

What is the probability of 4 digit numbers formed using the digits 1-6 divisible by 4?

Can anyone please guide me how to approach these kinds of problems with a solution for this problem ?
0
votes
3answers
121 views

Find the inverse using fast exponential algorithm?

I need to solve the following equation: $$x\equiv 17^{-1} \pmod{83}$$ Using...some "fast exponential algorithm". Well, that's the only information I have. Do you maybe know some fast exponential ...
0
votes
2answers
95 views

Linear congruence equations - how to determine the solutions

How can I determine the solutions of linear congruence equation solved using extended euclidean algorithm? For example: $$13x \equiv 12 \pmod{15}$$ $$\text{GCD}(13,15)=1=7(13)-6(15)$$ What's next? ...
1
vote
1answer
724 views

What is wrong with my solution of finding remainder of $50^{(51^{52})}$ when divided by 11?

I used the following method using remainder theorem. (I used method from here: Find the remainder of $128^{1000}/153$.) $$\begin{align} (50^{{51}^{52}})/11 & = (50^{2652})/11 \implies \\ ...