Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
23
votes
0answers
812 views
$4494410$ and friends
$4494410$ has the property that when converted to base $16$ it is $44944A_{16}$, then if the $A$ is expanded to $10$ in the string we get back the original number. ...
15
votes
0answers
183 views
A question on elementary number theory
Just came across the following question:
Let $S=\{2,5,13\}$. Notice that $S$ satisfies the following property: for any $a,b \in S$ and $a \neq b$, $ab-1$ is a perfect square. Show that for any ...
10
votes
0answers
280 views
How to prove there are an infinite number of squarefree numbers of the form $2^p-1$?
How to prove there are an infinite number of squarefree numbers of the form $2^p-1$, where $p$ is prime?
It is conjectured that all numbers of the form $2^p-1$ are squarefree. I've been having ...
9
votes
0answers
425 views
A Math trick with the number 246,913,578
Kindly see this trick question and help me know as to how it works:
The answer is always 123456789, how does it works? Can someone help me out here?
8
votes
0answers
123 views
A contest question
$p$ is an odd prime,denote $$f(x)=\sum_{k=0}^{p-1}\binom{2k}{k}^2x^k.$$
Prove that for every $x\in Z$,$$(-1)^\frac{p-1}2f(x)\equiv f(\frac{1}{16}-x)\pmod{p^2}.$$
This is a contest question,I do not ...
8
votes
0answers
217 views
Understanding Ramanujan's approach in his proof of Bertrand's Postulate
I've been reading through Ramanujan's proof of Betrand's Postulate and I'm not clear why he didn't state his proof in terms of $\varphi(2x) - \varphi(x)$
What would be wrong with this approach for ...
8
votes
0answers
312 views
Is it possible to find the digit sum of $n!$ ($n \in \mathbb{N} \text{ and } n \le100$) without actually computing the factorial?
Is it possible to find the digit sum of $n!$ ($n \in \mathbb{N} \text{
and } n \le100$) without actually computing the factorial?
I faced this problem in quantitative aptitude test which asks ...
7
votes
0answers
370 views
How many integer solutions to a diophantine equation
Starting with the equation:
$\frac{1}{a}+\frac{1}{b}=\frac{p}{10^n}$,
I reached the equation:
$10^{n-log(p)} = \frac{ab}{a+b}$.
Now given the positive integer $n$, for what integer values of $p$ ...
7
votes
0answers
225 views
My attempt to prove GCD exists
Please review my attempt to prove a theorem. Any mistakes you
point would be highly appreciated by me.
To prove the theorem, I'll be using the following
properties which I'm assuming have already ...
6
votes
0answers
52 views
Find a parametric formula to $n=(a^2+1)(b^2+1)$ in three distinct ways
I mentioned that the number $4420$ is expressible in the form $(a^2+1)(b^2+1)$ (where $a,b$ are positive integers) in three distinct ways,here is a list of these numbers:
...
6
votes
0answers
127 views
How prove this arithmetic progression cannot have terms of the form $2^m+3^n$ only?
Let $a_{i}\in \mathbb{N}$, $a_{i}\ge 1$, $i=1,2,\ldots,7$ be arbitrary, and such that
$a_{n+1}-a_{n}=d\neq 0,n=1,2,\cdots,6 $.
Then there exists $a_{\ell}$, $\ell=1,2,\ldots,7$, such that
...
6
votes
0answers
88 views
modulo of sums of consective powers
I am thinking of whether there is any pattern about sums of consective powers mod $m$.
Assume $m$,$n$,$k$ are integers.
Denote $$f_k(n)=1^k+2^k+\cdots+n^k,$$
The question is:
how does $f_k(n)$ ...
6
votes
0answers
323 views
A binary quadratic form and an ideal of an order of a quadratic number field
Let $F = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$.
We say $D = b^2 - 4ac$ is the discriminant of $F$.
If $D$ is not a square integer and gcd($a, b, c) = 1$, we say $ax^2 + bxy + ...
6
votes
0answers
141 views
How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?
Is there an easy way to compute the following question:
How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?
The only thing that ...
6
votes
0answers
184 views
Diophantine special problem
This is my another question on Diophantine equations.
Prove the following great and special problem.
Let $D$ and $k$ be positive integers and $p$ be a prime number such that $gcd(D, kp) = 1$. Prove ...
6
votes
0answers
394 views
Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?
Edward Waring, asks whether for every natural number $n$ there exists an associated positive
integer s such that every natural number is the sum of at most s $k$th powers of natural
numbers ...
5
votes
0answers
101 views
divisibility by powers of $2$ of diagonal sums of infinite latin square
This array is formed by placing integers such that each is the smallest such that the rectangle with it and the top left hand corner as opposite corners does not contain the same integer twice in any ...
5
votes
0answers
111 views
Carmichael number factoring
The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further ...
5
votes
0answers
112 views
Is there some exact form of $n$ for the number of $(i,j,k)$ satisfying $ijk = (n-i)(n-j)(n-k)$
For any positive integer $n$,
$i,j,k$ are also positive integers, and $0 <i,j,k < n$.
How many solutions of the form $(i,j,k)$ are there for the equation $ijk = (n-i)(n-j)(n-k)$?
5
votes
0answers
110 views
Question about a proof on p70 in Cassels' Local Fields
I'm trying to read the proof of
COROLLARY. The only solutions of
$x^2+7=2^m$ ($x,m \in \mathbb{Z}$) (6.15)
have $m=3,4,5,7,15$.
I don't see why there could be a + in $y\pm \alpha$ ...
5
votes
0answers
367 views
The Average Running Time Of Euclid Algorithm?
What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$?
It seems very hard to deduce from the recurrence
$T(m,n) = T(n, m ...
4
votes
0answers
54 views
$\{a^{k_1}\}=\{a^{k_2}\}=\{a^{k_3}\}$
Let $a\in\mathbb{R}\setminus\mathbb{Z}$. Prove that there not exist three distinct $k_1, k_2, k_3\in\mathbb{N}$ such that $\{a^{k_1}\}=\{a^{k_2}\}=\{a^{k_3}\}\neq 0$, where $\{x\}=x-\lfloor x ...
4
votes
0answers
63 views
Determine the least prime $p$ for which $2^{p-1} \equiv 1 \pmod {p^2}$.
Determine the least prime $p$ for which $2^{p-1} \equiv 1 \pmod {p^{2}}$ .
4
votes
0answers
88 views
For every partition $\pi$ of a fixed integer $n$, $\sum{F(\pi)}=\sum{G(\pi)}$
I need to prove the following question.
For every partition $\pi$ of a fixed integer $n$, define $F(\pi)$=number of occurrences of 1 as a summand, and $G(\pi)$=no. of distinct summands in the ...
4
votes
0answers
90 views
Existence of an n digit prime
I know that there are proofs that for any $n\geq 1$ there is at least one prime $p$ satisfying $i\cdot n\leq p\leq (i+1)n$ for $i\in\{1,2,3\}$. But are there any simpler proof(s) that there is always ...
4
votes
0answers
126 views
Wilson's Theorem and related identities
The (little) Fermat Theorem:
if $p$ is prime then $a^{p-1}=1\ \text{mod} \ p$ for whatever $a$
may be easily understood as a consequence of the group structure of multiplication on integers mod ...
4
votes
0answers
211 views
Properties of Greatest Common Divisor
I need to prove some GCD properties:
$i$) $\quad\gcd(a,b)=\gcd(b,a)$
$ii$) $\quad\gcd(ca,cb)=c\gcd(a,b)$
$iii$) $\quad\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))$
Proof $(i)$:
Let ...
4
votes
0answers
79 views
Show that if we have a product of distinct odd primes m, then they lie in half of b modulo m.
I'm having a lot of difficultly understanding the approach I should use for this problem. I was wondering if anyone would be able to provide some assistance.
Show that if m = p1....pr is a product of ...
4
votes
0answers
64 views
Integer weights used to cover all numbers from 1 to N with redundancies in case of breakage
Bachet's Problem (arxiv) is a famous problem where we have to find the smallest set of positive integers such that they measure every number between 1 and 40. This can be generalized to every integer ...
4
votes
0answers
224 views
Bijection between an ideal class group and a set of classes of binary quadratic forms.
Let $F = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$.
We say $D = b^2 - 4ac$ is the discriminant of $F$.
If $D$ is not a square integer and gcd($a, b, c) = 1$, we say $ax^2 + bxy + ...
4
votes
0answers
205 views
Finding the sum of the digits of $3^{1000}$
Can we work out the sum of the digits of the number $3^{1000}$ without any program?
I just means the way of pure mathematics.
I'm interested in learning more way to solve this problem.Let's solve it ...
4
votes
0answers
217 views
Digital Numbers using all digits from 1-9
Call a number a digital number if it consists of all the digits from 1-9, each used exactly once.
What is the probability that a digital number will be divisible by 7 ?
What is the probability that a ...
4
votes
0answers
188 views
Sum of floor function $\pmod{n}$
Let $n$ be a positive integer. Let $a$ be a nonzero integer such that $\gcd(a,n)=1$.
How to show that $$\frac{a^{\phi (n)}-1}{n} \equiv \sum_i \frac{1}{ai} \left \lfloor \frac{ai}{n} \right \rfloor ...
4
votes
0answers
75 views
Finding a closed expression for a calculated value.
Sometimes, when getting some numerical results when investigating number theory sequences with a computer, I find myself suspecting that a decimal value ($a$) I have found might be a quadratic ...
4
votes
0answers
112 views
Are $3$ and $11$ the only common prime factors for $\sum_{k=1}^N k!$ for $N\geq 10$?
The question was stimulated by this one:
When you look at values of $\sum_{k=1}^N k!$ for $N\geq 10$, you'll always find $3$ and $11$ among the prime factors, due to the fact that
$$
...
4
votes
0answers
484 views
Solve Polynomial Congruence mod $89^2$
Solve $3x^2+6x+5\equiv 0\pmod{89^2}$.
To do this, I first solved $3x^2+6x+5\equiv 0\pmod{89}$.
This has a solution since $3x^2+6x+5 = 3(x+1)^2 + 2$ and $3(x+1)^2 \equiv -2 \pmod{89}$ has a ...
4
votes
0answers
119 views
Fractional iteration of the Newton-approximation-formula: how to resolve one unknown parameter?
For my own exercising I tried to find a closed form expression for the Newton-approximation algorithm, beginning with the simple example for getting the squareroot of some given $ \small z^2 $ by ...
4
votes
0answers
268 views
On the equation $m^3-m^2+1 = n^2$
(i) How can I find all positive integers $m$ such that $m\equiv 4 \pmod 7$ and $m^3-m^2+1$ is a perfect square?
(ii) Is there a method to solve this equation over positive integers:
$$m^3-m^2+1 = ...
4
votes
0answers
198 views
How to find the number of continued fraction from a periodic representation?
Problem
Find the number that represented by $[2,2,2 \ldots]$
I know it wasn't difficult, but I was absent the last two classes. So I just want to make sure that I got it right.
My attempt was,
...
3
votes
0answers
73 views
+50
Only 3 $n$ where $q=\left\lfloor (2 p_n+p_{n+2}) (p_{n}+p_{n+1}+p_{n+2})\over p_{n}\right\rfloor,\;\text{isPrime}(q)$?
Consider: $$q=\left\lfloor (2 p_n+p_{n+2}) (p_{n}+p_{n+1}+p_{n+2})\over p_{n}\right\rfloor,\;\text{isPrime}(q)$$
where $p_n$ denotes the $n$th prime.
Other than: $$n=6\quad\text{or}\quad ...
3
votes
0answers
52 views
On Sixth Powers $x_1^6+x_2^6+\dots+x_6^6 = z^6$
Fourteen years ago, in 1999 (has it been that long?) Merignac started a search for,
$$x_1^6+x_2^6+\dots+x_6^6 = z^6$$
using the five congruence classes,
$$\begin{aligned}
...
3
votes
0answers
43 views
Generalizing Ramanujan's 6-10-8 Identity
Ramanujan's 6-10-8 Identity can be succinctly given. Define,
$$F_k = a^k+b^k+c^k-(d^k+e^k+f^k)$$
If $F_2 = F_4 = 0$ and $a+b+c = d+e+f = 0$, then Ramanujan found that,
$$64F_6 F_{10} = 45F_8^2$$
...
3
votes
0answers
47 views
Does a quasiperfect number exist? (n = sum of its divisors $\ne$ n,1)
Just like proper subsets of a set A are considered all subsets of A excluded A itself and $\emptyset$, some authors define proper divisors of an integer n all divisors but 1 and n itself: MathWorld, ...
3
votes
0answers
70 views
$M_n=2^n-1$ Mersenne numbers in mathematics
Did the Mersenne numbers turn out to be interesting in other fields of mathematics besides the Numbers Theory?
In other words, the function $M(n)=M_n$
where
$$M_n=2^n-1$$
or the recursive realtion
...
3
votes
0answers
100 views
sum of digits in different bases
Given a natural number, What is the maximal natural number below it, whose sums of digits in base 10 and base 2 are the same?
Is there a clever algorithm to do this aside from the brute force search?
3
votes
0answers
103 views
Would love some criticism on a couple divisibility proofs
Horrible at proofs would love some help getting into better form! Please and thank you all. Critiques welcome.
1st question
Let $a$ and $b$ be positive integers and we write the result of the ...
3
votes
0answers
96 views
Show if a product of coprime numbers is a perfect square, so are the numbers - without FTA
I want to prove: $$\text{If }\gcd(a,b)=1\text{ and }ab=n^2,\text{ then }a,b\text{ are also perfect squares.}$$ Assume everyone is a positive integer, etc. Unless I'm deluding myself, this is pretty ...
3
votes
0answers
125 views
Must be rational number
Let $a$, $b$ positive rational number. Suppose that there exist two odd positive integers $p$, $q$ such that $\sqrt[p]{a}+\sqrt[q]{b}$ is rational. Prove that both $\sqrt[p]{a}$ and $\sqrt[q]{b}$ are ...
3
votes
0answers
61 views
Polynomial bound
Let $P(x)=a_4 x^4+a_3 x^3+a_2 x^2+a_1 x+a_0$ such that
$$\forall i\in \{0, 1, 2, 3, 4\};\phantom{;}a_i\in\mathbb{Z} \wedge |a_i|\leq T\phantom{.}(T\in\mathbb{Z}^+ )$$
Suppose that $P(x)> 0$ for all ...
3
votes
0answers
79 views
Limit involving sums of the Von-Mangoldt function
Can someone show that the limit bellow approaches 1/2? Can you also prove that it does, with out using the prime number theorem?
$$ \lim_{n\to\infty} \frac{\sum\limits_{k=1}^n \Lambda(k) ...
