New answers tagged divisibility
4
votes
Prime Divisors of $x^2 + 1$
Another more elementary way to think about it is using Lagrange's Theorem.
Let $p$ be an odd prime that divides $x^2+1$ ($p$ must be odd because $x^2+1$ is odd). This means that
$$
x^2 \equiv -1 \pmod ...
- 51
1
vote
How did Euler know $X=6^{128} + 1$ is divisible by $Y=257$
$Y=257=2^8+1\mid(2^8+1)(2^8-1)(2^{16}+1)(2^{32}+1)(2^{64}+1)=2^{128}-1$,
so $2^{128}\equiv1\pmod Y$,
so $\left(\dfrac2{257}\right)=1$ by Euler's criterion.
(Alternatively, $\left(\dfrac2{257}\right)=1$...
- 62k
-1
votes
How to approach this divisibility problem on polynomial
Let the first polynomial be expressed as it's sum since it's in a geometric progression.
i.e. x^9999 + x^8888 ... x^1111 + x = x^11110 - 1 / x^1111-1
similarly,
let the second polynomial be expressed ...
12
votes
Accepted
How did Euler know $X=6^{128} + 1$ is divisible by $Y=257$
Euler has given the answer himself via the Paper here :
"Observations on a theorem of Fermat and others on looking at prime numbers"
At the Conclusion , Euler claims :
"Theorem V. $3^n +...
- 13.4k
1
vote
problem about $a^2+b^2=c^2+d^2$ and divisibility
This is part of an old result of Euler which shows that $\,n\,$ is composite if it has two essentially distinct representations as sums of squares (the proof constructs a proper factor of $\,n\,$ via ...
- 276k
1
vote
Accepted
Let $p$ and $q$ be prime numbers such that a function is a multiple of $q$. Prove that $q>p$
We can use Fermat's Little Theorem to say that $a^{q-1} \equiv 1 \pmod q$. Now since $q$ is a prime that divides $2^p-1$, we can set $a$ equal to $2$ to obtain $2^{q-1} \equiv 1 \pmod q$.
Now I claim ...
- 64
4
votes
Accepted
Proving that a sum is a composite number
Assuming that the intended question is "is the long sum prime":
We remark that $a\,|\,b$ implies that $(n^a-m^a)\,|\,(n^b-m^b)$. You used this remark in showing that $3^5-2^5$ divided $3^{...
- 72.5k
3
votes
Proving that a sum is a composite number
Each term in the second bracket is at least $1$, and there are at least two terms in the bracket. So, their sum cannot be $1$. Hence, the first bracket cannot be the full number on the right, and thus ...
- 7,807
0
votes
Proving that a sum is a composite number
We need to think outside the box, and consider the definition of prime numbers rigorously.
If $n$ is prime, $1$ and $n$ are the only factors of $n$. $1 \times n = n$. Consider $a \times m=n$
If $a=1$,...
- 157
-1
votes
Find the highest natural number which is divisible by $30$ and has exactly $30$ different positive divisors.
Since the number is divisible by 30 the number (let it be $a$) will be of the form $a=2^{\alpha_1}3^{\alpha_{2}}5^{\alpha_{3}}$
The number of proper divisors of a number is given by
$$\sigma(a) = \...
0
votes
Accepted
Proving $2^{\lfloor n/2 \rfloor}$ divides the permanent of any $n\times n$ $(1,-1)$ matrix by induction and Laplace expansion
This solution was inspired by @darij grinberg comment.
The claim is clearly true for $n=1$ and $n=2$.
Let $A\in \Omega_n$.
By Laplace expansion, we have
$$\operatorname*{per}(A) = \sum_{j = 1}^{n} a_{...
- 844
-1
votes
Find all integers n such that $2n-1 \mid n^3-3n^2+4$.
According to the hint from John Omielan's comment,
if $2n-1$ divides $n^3-3n^2+4$, then $2n-1$ divides $8(n^3-3n^2+4)$.
Using polynomial division, $8n^2-24n^2+32=(2n-1)(4n^2-10n-5)+27$.
Thus $2n-1$ ...
- 62k
0
votes
Determine the number of factors for extremely large numbers.
You can verify that a 1000 digit number is prime and therefore has two factors, of course proving a number is prime gives you the factorisation instantly.
You can verify that a 1000 digit number is ...
- 10.3k
1
vote
Why is the sum of the digits in a multiple of 9 also a multiple of 9?
Every number can be written as follows:
$$a = 10^n \cdot a_n + 10^{n-1} \cdot a_{n-1} + ... + 100 \cdot a_2 + 10 \cdot a_1 + a_0$$
(where $a_0$ is the last digit, $a_1$ the last but one, ... and $a_n$ ...
- 2,868
1
vote
Why is the sum of the digits in a multiple of 9 also a multiple of 9?
It seems like this is a natural candidate for proof by induction. Suppose $n=9k$ is a multiple of $9$. Clearly the sum of the digits of $n$ are divisible by $9$ for $k=1$. Suppose that this holds for ...
- 61
0
votes
Accepted
Is the proof of the theorem shown valid, and, if not, how might the proof be fixed?
You're correct the proof you've shown is flawed. In particular, with $i = p$ and $j = 0$ then, as you've stated, $r_p = r_0$ since the terms are $a + pk$ and $a$, respectively, with a difference of $...
- 50.5k
2
votes
Accepted
If $b=\gcd(a,b)q$ then $\gcd(a,q)=1$
This is not true. Take $b=4$ and $a=2$ and so $\gcd(2,4)=2$ and thus $q=b/(\gcd(a,b)) = 4/2=2$. Then $\gcd(a,q)=\gcd(2,2)=2$.
To generalize: If for some prime $p$ and some integer $e \ge 2$, all three ...
- 21.5k
2
votes
A simple question on AP , only issue , answer does not match
You used inclusion-exclusion principle. However, intersection of multiples of $4$ and multiples of $6$ is multiples of $12$, not multiples of $24$. Multiples of $12$ in the set $[100, 300]$ is from $...
- 406
Top 50 recent answers are included