Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

0
votes
3answers
55 views

Understanding the sieve of eratosthenes

Wikipedia, explains the basic algorithm of eratosthenes and several pages such as this, explain the refinements made on the sieve. But the thing I'm having a hard time to find is: Why does the next ...
3
votes
4answers
138 views

Prove that $x^4-y^4=1996$ has no integer root.

Prove that $x^4-y^4=1996$ has no integer root. $LHS=(x-y)(x+y)(x^2+y^2)=1996$ Now we have to consider all possible decompositions of $1996$ resulting in a non Linear system of equations seemingly ...
0
votes
2answers
51 views

Is 2 both a prime and a highly composite number?

I came across the definition of a highly composite number yesterday as a positive integer that has more divisors than any positive integer smaller than it. And, then I realised it would give 2 a very ...
2
votes
0answers
58 views

Discriminant of a polynomial definition

Why is the discriminant of a polynomial defined as the product of squared differences of roots? How do I intuitively understand it? Why was this definition chosen?
0
votes
1answer
47 views

Following the previous question: Existence of the natural density …

Following the previous question: Let $A=\{a_n\}$ is a strictly-increasing sequence of positive integer. The natural density of this sequence is defined by $\delta(A)=\lim_{n\rightarrow \infty} \frac{...
1
vote
1answer
25 views

Perfect square palindromic numbers

A palindromic number is one which when expressed in base $10$ with no leading zeros, reads the same left to right and right to left. For example, $44944$ is a (base 10) palindrome. I can find quite ...
2
votes
6answers
117 views

Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can't be reduced.

Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can't be reduced. Attempt: It can't be reduced when $\gcd(12n-6,10n-3)=1$ Here $(a,b)$ denotes $\gcd(a,b)$ $$(12n-6,10n-3)=(12n-6,2n-3)=(...
0
votes
2answers
59 views

Finding the value of abc

The ratio of the six-digit numbers $abcabc$ and $ababab$ is 55:54. Find the values of the digits $a$, $b$ and $c$.
6
votes
0answers
71 views

Making perfect cube from factors of $20!$

At least how many different factors of $20!$ must we choose so that we can always find some subset whose product is a perfect cube? For example, if we choose $\{2,3,5,7,11,13,17,19,22,26,34,38\}$, ...
8
votes
1answer
89 views

Numbers whose reciprocals sum to $1$

What are all the numbers that can be written as $a_1+a_2+\dots+a_n$, where $a_1,\dots,a_n$ are positive integers such that $\frac{1}{a_1}+\dots+\frac{1}{a_n}=1$? For instance, such numbers include $4=...
0
votes
2answers
57 views

Can an irrational number be expressed as a sum of other irrational numbers, at least one of which is not an integral multiple of the required number?

For example, $\pi = Ae + B\sqrt 2+ \cdots$ ($A,B,\ldots\in\mathbb R$) (Equations like "$\pi = 3\pi - 2\pi$" are not allowed.)
4
votes
2answers
78 views

How can we create arbitrarily long instances of the Euclidean algorithm?

How can we create arbitrarily long instances of the Euclidean algorithm? What kind of numbers are useful? What is the relationship between the size of these numbers and the number of steps?
11
votes
6answers
2k views

Why does the Euclidean algorithm always terminate?

Why does the Euclidean algorithm always terminate? Can we make this effective by bounding the number of steps it takes in terms of the original integers?
9
votes
1answer
135 views

Is $n^7 - 77$ ever a Fibonacci number?

As the question title suggests, is $n^7 - 77$ ever a Fibonacci number, where $n$ is a integer?
1
vote
1answer
76 views

Regarding irrationality of $\sqrt{5}$

In the proof of irrationality of $\sqrt{5}$, Hardy and Wright define $x=\frac{\sqrt{5}-1}{2}$. From that I know $1-x=x^2$. But then the authors say that when $1$ is divided by $x$ the remainder is $1-...
1
vote
3answers
101 views

Last digit of $2^{9^{100}}$

If the last digit of $9^{9^9}$ is $z$ then find the last digit of $2^{z^{100}}$. My try:- As unit digit of $9^{\text{odd}}$ is $9$, then $z=9$. Then we are asked to find the last digit of $2^{9^{100}...
8
votes
4answers
250 views

Is $77!$ divisible by $77^7$?

Can $77!$ be divided by $77^7$? Attempt: Yes, because $77=11\times 7$ and $77^7=11^7\times 7^7$ so all I need is that the prime factorization of $77!$ contains $\color{green}{11^7}\times\color{blue}...
2
votes
1answer
24 views

If $N = q^k n^2$ is an odd perfect number, is it possible to have $I(n^2) = I(q^k) + c$, for some constant $c > 0$?

The title says it all. If $N = q^k n^2$ is an odd perfect number, is it possible to have $I(n^2) = I(q^k) + c$, for some constant $c > 0$? Here $I(x)$ is defined to be the ratio $$I(x) = \...
0
votes
3answers
38 views

Using Fermat's Little Theorem to compute vast numbers

I was given a how problem set with the following problems to solve (I'm allowed to use a calculator for all operations excluding exponentiation): $3^{23} + 3 ≡ 5^{37} − 4 \pmod 7$ $1,000,001^{999,...
1
vote
3answers
87 views

How to prove by induction that $4^{2n}-3^{2n}-7$ is divisible by 84 for any n starting from 1?

How to prove by induction that $4^{2n}-3^{2n}-7$ is divisible by 84 for any n starting from 1 ? Take n=1 and prove for the base case, assume its true for some n, then the third step went like this: $$...
1
vote
0answers
89 views

How to factorize $49403$

I want a way without calculator that factorizes $49403$.I mean a way like that we factorize $391$. $391=20^2-3^2=(20-3)(20+3)=17*23$ For $49403$ we can do this: $49403=258^2-131^2=(258-131)(258+131)...
5
votes
1answer
96 views

How many natural numbers $x\leqslant 21 !$ there are such that $\gcd(x,20!)=1$

How many natural numbers $x\leqslant 21 !$ there are such that $\gcd(x,20!)=1$ Attempt: I used this methode and I have found that: $21!$$=2^{18}\times3^{9}\times5^{4}\times7^{3}\times11\times13\...
1
vote
1answer
72 views

How to factorize a number into prime numbers

I have to compute the Legendre symbol $4307 \choose 7549$, so I have to factorize $4307$ into prime numbers. Is there any mathematical shortcut to do it?
4
votes
3answers
88 views

Prove that: $x^2+y^2+z^2=2xyz$ has no answer over $\Bbb{N}$

Prove that: $x^2+y^2+z^2=2xyz$ has no answer over $\Bbb{N}$ $$LHS=(x+y+z)^2-2(xy+yz+xz)=2xyz \implies (x+y+z)^2=2(xy+yz+xz)+2xyz$$ now what??
1
vote
3answers
51 views

Weird Number patterns thinking process [closed]

The number pattern is -1 , 8 , -27 , 64 , -125 Find an expression for the nth term of the sequence . I'm been doing it by the guessing method for a few mins and couldn't get the answer . Can I get ...
0
votes
0answers
24 views

Is it conjectured there infinitely primes $p$ such that M($p$) is a Mersenne Prime, where p is of an arithmetic progression?

Are there infinitely many primes $p$ of the form $an+d$ for fixed $a$ and $d$ coprime, and that $2^p-1$ is also prime? In other words, there are infinitely many primes $p$ $=$ $a$ $\pmod d$ ($a$ and ...
1
vote
2answers
101 views

How to read a proof? [closed]

As I go deeper and deeper into upper division math courses, I find some proofs to be very challenging to understand. Right now I am trying to understand Gauss's lemma in number theory and I can't ...
0
votes
1answer
27 views

Computing the Legendre symbol $6 \choose 11 $

Compute the Legendre symbol $6 \choose 11$ By euler's critetion, ${6 \choose 11}=-1$, but ${6 \choose 11}={3 \choose 11 }{2\choose 11}=-1*-1=1$. I am confused about that result.
35
votes
9answers
2k views

Is difference of two consecutive sums of consecutive integers (of the same length) always square?

I am an amateur who has been pondering the following question. If there is a name for this or more information about anyone who has postulated this before, I would be interested about reading up on it....
0
votes
1answer
47 views

Proof that $(2K^2-b^2)^{1/2} \subseteq\frac{x^2-2}{(z+y)}$

I figured out a interest property when trying to solve: Create a sequence such that $K,a,b$ is an integer and the Greatest Common Denominator of $a \hspace{2mm}\&\hspace{2mm} b=1$; $$K=(\...
5
votes
6answers
116 views

Factoring out a $7$ from $3^{35}-5$?

Please Note: My main concern now is how to factor $7$ from $3^{35}-5$ using Algebraic techniques, not how to solve the problem itself; the motivation is just for background. Motivation: I was trying ...
9
votes
0answers
50 views

What to keep in mind when attempting proof of basic properties of divisibility/what techniques are useful/what's the intuition for showing them?

So I am currently trying to prove some basic divsiibility relations, as follows. If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$. If $a \mid b$ and $s \in \mathbb{Z}$, then $a \mid sb$. ...
8
votes
0answers
47 views

Intuition behind the proof of the validity of the Euclidean algorithm

As the question title suggests, could anybody explain to me their intuition behind the proof of the validity of the Euclidean algorithm?
2
votes
1answer
26 views

ceiling of an expression

If we need to find the ceiling of this expression (A-11)/100 then is it correct to simply write the above expression as ...
14
votes
4answers
705 views

Smallest future date which involves no repetition of a digit in the format DD/MM/YYYY [closed]

What is the smallest future date which involves no repetition of a digit in the format DD/MM/YYYY for the year? What is your approach?
0
votes
2answers
29 views

Prove that If $m'$ is a common multiple of $s$ and $t$, then $m | m'$. Here $m$ is the LCM of $s$ and $t$.

Prove that If $m'$ is a common multiple of $s$ and $t$, then $m | m'$. Here $m$ is the LCM of $s$ and $t$. Although the statement is intuitively clear to me I don't know how to prove.
0
votes
3answers
61 views

Prove by induction that $a^{4n+1}-a$ is divisible by $30$ for any $a$ and $n \geq 1$ [closed]

I don't know how to approach this problem since I don't know how to factor out $a$ which can be any number larger than $1$ in naturals, and that is the only approach I know for these kind of problems.
4
votes
3answers
119 views

Prove by induction that $n^5-5n^3+4n$ is divisible by 120 for all n starting from 3

I've tried expanding $(n+1)^5-5(n+1)^3+4(n+1)$ but I end up with $120k+5(n^4+2n^3-n^2-2n)$ where k is any positive whole number, and I can't manipulate $5(n^4+2n^3-n^2-2n)$ to factor with 120.
0
votes
1answer
41 views

Order chicken wing boxes

You get a chicken wing boxes with either (3,8,20) items - is there a maximum number that you cannot buy and if so, which one?
0
votes
0answers
70 views

Remainders of repeating digits

What will be the remainder when $122333444455555\ldots1313141414141$(Total of $100$ terms)divided by $7$? My method is that the above sequence can be written as $10^{99} + 22\times10^{97} +333\...
0
votes
0answers
21 views

total numbers from 1 to N whose second smallest number is known

We are given a value N. We need to find how many numbers from 1 to N have a number i as the second smallest non divisor if their smallest non divisor is j? Let us say N=10 .The second smallest non ...
3
votes
2answers
62 views

Find all the numbers $a,b$ such that $\frac{2a-b}{2a+b}$ can't be reduced

Find all the numbers $a,b$ such that $\frac{2a-b}{2a+b}$ can't be reduced Attempt: For $a:$ $$\gcd(2a-b,2a+b)\\ =\gcd(2a-b,4a)\\ \boxed{\{a:4a\nmid2a-b\}}$$ For $b:$ $$\gcd(2a-b,2a+b)\\ =\gcd(2a-...
0
votes
1answer
18 views

Given any $r \in \mathbb Q$, there is $m \in \mathbb Z$ such that $m \le r < m + 1$

Suppose the set $S$ contains all $n \in \mathbb Z$ such that $n > r$ for any $r \in \mathbb Q$. By Archimedes, there are some $m, n \in \mathbb Z$ such that $n > r > m$ for any $r \in \mathbb ...
0
votes
5answers
65 views

Prove divisibility by induction

Prove that $5^{2n+1}2^{n+2}+3^{n+2}2^{2n+1}=19k$ for all $n$ natural numbers. I have tried writing 19 as a sum of two numbers and then proving that the LHS is a sum of the form $Ax+By=(A+B)k$but I ...
1
vote
5answers
90 views

Prove by induction that $3^{2n+3}+40n-27$ is divisible by 64 for all n in natural numbers

I cannot complete the third step of induction for this one. The assumption is $3^{2n+3}+40n-27=64k$, and when substituting for $n+1$ I obtain $3^{2n+5}+40n+13=64k$. I've tried factoring the expression,...
1
vote
1answer
42 views

Calculation for linear congruential generator: Setting up equations

Given a linear congruential random number generator $x_{n+1} = (a \cdot x_n + c) \bmod m.$ We are given the first three values $x_0 = 5, x_1 = 3,x_2 = 16$ and the 50-th values $x_{50} = 2,$ what can ...
5
votes
1answer
83 views

Why is the smallest Pythagorean triple $(x,y,z)=(3,4,5)$ not close (in ratio $x/y$) to any other small triple?

The table below lists the primitive Pythagorean triples $x^2+y^2=z^2$ with $z<100$ in ascending order of the ratio $x/y$. The final column shows the difference between each ratio and the preceding ...
0
votes
0answers
70 views

Primality test for $F_n(10)=10^{2^n}+1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Theorem Let $F_n(2)=2^{2^n}+1$ ...
0
votes
1answer
29 views

Question about reduced residue system

Let $1,2,.......,p-1$ be a reduced residue system mod $p$ where $p$ is a prime number. If $\gcd\left(k,p\right)=1$ for an integer $k$ then we can say $k,2k,\dots,k(p-1)$ is also a reduced residue ...
0
votes
0answers
38 views

Need help with the explanation of a theorem

http://people.ucsc.edu/~yorik/Math110/PDF/QuadRec.pdf My question is in theorem 3. I understand until it says $a={p-1}/2$ if $p \equiv 1(\mod 4)$ and $a=p-(p-1)/2$ if $p \equiv 3(\mod 4)$. Why is ...