3
votes
2answers
61 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
2
votes
0answers
39 views

Diophantine: $x^3+5=y^5$

Find all integers $x$ and $y$ such that $x^3+5=y^5$. I found this after solving the equation $3^a+5=2^b$. For this equation, since $(a,b)=(3,5)$ is a solution, it is possible to write it as ...
1
vote
0answers
34 views

Multiplicative order: an exercise

I've got this problem: Determine an integer with (exactly) multiplicative order $22$ mod $1331$ Is there a general way to procede in any case with this kind of exercises? Thank you!
2
votes
1answer
42 views

Silly number theory questions I can't prove.

I know if $gcd(r,s)=1$ then $1=as+bs$ for some intgers $a,b$. Here's what I want to know: which numbers can be written as $as+bs$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
0
votes
0answers
29 views

Sum of digits of numbers in a range

Given an integer N. For each pair of integers (L, R), where 1 ≤ L ≤ R ≤ N we can find the number of distinct digits that appear in the decimal representation of at least one of the numbers L L+1 ... ...
-2
votes
0answers
47 views

Count Triangular Triplets [on hold]

Given a range [L,R] we need to calculate numbers of such triplets [A,B,K] which follows A+B=K where A,B are any two triangular numbers and K must be in an ...
3
votes
3answers
116 views

Infinitude of prime numbers

Everyone knows that there is an infinitude of primes. I know the Euclide, the Euler and the Erdos proofs. But are they the only known proofs ? I will try, here, to present a fourth one : Let the ...
0
votes
2answers
49 views

how shall i find the $n$-th term of this,

How shall I find the $n$-th term of this: $\sqrt{1+2}$ $\sqrt[3]{1+2+3}$ $\sqrt[4]{1+2+3+4}$ $\sqrt[5]{1+2+3+4+5}$ $\sqrt[6]{1+2+3+4+5+6}$ $\sqrt[7]{1+2+3+4+5+6+7}$ all the way to ...
0
votes
1answer
34 views

Order of an integer

Why is it true that: if a has order 3 modulo p then $1+a+a^2 \equiv 0 \, \text{mod}\, p$ Thank you!
1
vote
1answer
27 views

Another exercise in number theory

I wanted to ask you to help me with this exercise in numer theory. Here it is: If $g$ is a primitive root modulo $p$ and $d|p-1$, show that $g^{(p-1)/d}$ has order $d$. Show also that $a$ is a ...
0
votes
0answers
26 views

Another question/observation about Mersenne numbers and Euler's totient function

This is a follow up to this question Upper bound for Euler's totient function on composite Mersenne numbers and an ongoing project with lots of questions related to Mersenne numbers. I'm sorry if ...
0
votes
0answers
26 views

Counting/bounding number of relatively prime pairs?

I'm wondering if anyone knows of results counting or bounding the number of relatively prime pairs in two subsets of positive integers. In particular: Given $A = \{a \in \mathbb{Z} | m_1 \leq a \leq ...
0
votes
1answer
36 views

Solution to Diophantine equation with constraint.

solve the following equation over $z_x,z_y$ \begin{align} &az_x=bz_y\\ &\text{s.t. } a,b,z_x,z_y \in \mathbb{Z} \text{ and } 1 \le z_x \le N \text{ and } 1 \le z_y \le N \end{align} How ...
1
vote
1answer
48 views

Residue class of a huge repunit modulus a huge number

Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want ...
2
votes
1answer
56 views

Hard Simultaneous Diophantine Equations

Find all positive integers $a,b,c,d,e,f$ such that : $de^2=ab^2+1$ and $df^2=ac^2+1$. I tried subtracting them, it factors quite nicely. But after that, haven't a clue. I'm not sure if it's even ...
2
votes
1answer
117 views

Are there any “obviously” true propositions in number theory?

After all efforts spent on wrong proofs of famous number theory conjectures and theorems like Goldbach's or Fermat's last theorem, could one find some simple statements (might be correct ones) whose ...
4
votes
0answers
154 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
2
votes
0answers
28 views

floor function inequality $\frac{3c-3n-3}{2n+3} \geq \lfloor\frac{3c-3n}{2n+3}\rfloor$

I want to prove following statement: $$\forall K\in \mathbb R \exists c\in \mathbb N c\geq K s.t.\forall n\in \left\{1,2,...,c-1\right\}: \frac{3c-3n-3}{2n+3} \geq \lfloor\frac{3c-3n}{2n+3}\rfloor$$ ...
0
votes
0answers
36 views

Hard Diophantine: $ xy-\frac{(x+y)^2}{n}=n-4 $

Solve in positive integers $x,y$: $ xy-\frac{(x+y)^2}{n}=n-4 $ $n>4$ is a given positive integer. I cannot even solve in the case $n=5$. I have been able to find $x,y$ and construct $n$ using ...
3
votes
2answers
121 views

Solving $x^3+y^3=x^2y^2+1$ in non-negative integers

I wanted to solve $x^3+y^3=x^2y^2+1$ in non-negative integers. First I set $a=x+y$ and $b=xy$ to get $b^2+3ab+1=a^3$. View as a quadratic in $b$, the discriminant = $4a^3+9a^2-4$, which needs to be a ...
0
votes
1answer
52 views

Solve for x,y: $x^2+1=2y^2$

Solve for integers $x,y$ such that $x^2+1=2y^2$? I tried factoring as $(x-y)(x+y)=(y-1)(y+1)$ but couldn't continue from here, I would appreciate any help. Thanks!
2
votes
2answers
57 views

Diophantine: $px^2+2=y^2$ where $p\in \mathbb{P}$

Solve the Diophantine Equation: $px^2+2=y^2$, where $p$ is a prime number and $x,y$ integers. I tried this for ages but didn't get anywhere, but I don't know any advanced machinery since I am only in ...
0
votes
0answers
42 views

Number of prime factors of Mersenne numbers

Let $p$ be a prime and let $M_p = 2^p-1$. Is it known whether the number of prime factors of $M_p$ is unbounded above as $p \to \infty$? Also do the probabilities estimating the chance that $M_p$ is ...
5
votes
1answer
105 views

Fermat: Prove $a^4-b^4=c^2$ impossible

Prove by infinite descent that there do not exist integers $a,b,c$ pairwise coprime such that $a^4-b^4=c^2$.
2
votes
2answers
121 views

If $~a^3 + b^3 = c^3~$ has nonzero integer solutions and $~c-b~$ is a cubic number and $~c-b \neq 1$

If $~a^3 + b^3 = c^3~$ has nonzero integer solutions, because: $c^3 - b ^ 3 = (c - b)((c - b) ^ 2 + 3cb) = a ^ 3,\quad (1)$ if $~c-b~$ is a cubic number and $~c-b \neq 1~$, divide both side of ...
1
vote
4answers
117 views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
1
vote
1answer
30 views

Division algorithm for the natural numbers.

I am trying to prove the following statement from Tao's analysis book. Definition of multiplication $ab++=ab+b$. Definition of addition $(a++)+b=(a+b)++$. Let $n$ be a natural number, and let $q$ ...
3
votes
2answers
56 views

Induction on GCD problem [duplicate]

This is a two part question Given $\gcd(a,b) = 1$ consider $$\gcd \left( \frac{a^n - b^n }{a-b}, a- b\right) $$ It appears that the value of this is always equal to $n$ or $1$. How to prove it? ...
3
votes
4answers
123 views

Tricky descent proof

EDIT: Please see EDIT(2) below, thanks very much. I want to prove by infinite descent that the only positive integer factors of integers of the form $a^2+3b^2$ have the same form. For example, ...
2
votes
3answers
69 views

Finding the square root $s$ of 1293 modulo 3337.

If $3337 = 47 \cdot 71$, how do you find the square root $s$ of $1293 \pmod { 3337}$ (where $0 < s < 3337$). I understand that $m = 3337 = p \cdot q$ and $p=47$ and $q=71$, but not sure where ...
1
vote
3answers
141 views

How to prove $~(c - b) ^ 2 + 3cb = x^3~$ has no nonzero integer solutions?

I'm trying solve: $~a^3 + b^3 = c^3~$ has no nonzero integer solutions. Only one problem left: because $c^3 - b ^ 3 = (c - b)((c - b) ^ 2 + 3cb) = a ^ 3,\quad (1)$ if $~c-b~$ is a cubic number, ...
6
votes
1answer
53 views

Torsion of finitely generated $\mathbb Z_ \ell$-module finite?

Let $M$ be a finitely generated $\mathbb Z_ \ell$-module, where $\ell$ is a prime number and $\mathbb Z_\ell$ is the ring of $\ell$-adic integers. Let $T$ be its torsion submodule. Is $T$ finite? In ...
1
vote
2answers
43 views

Can't understand source of constant for prime counting function:

Consider the prime counting function $$ \pi(x) = \ the \ number \ of \ primes \ less \ than \ or \ equal \ to \ x$$ It is well known due to the sieve eratosthenes that given an integer $n$ and the ...
1
vote
1answer
26 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
-2
votes
2answers
312 views

Is this a solution for the problem: $\ a^3 + b^3 = c^3\ $ has no nonzero integer solutions?

Is this a solution for the problem: $\ a^3 + b^3 = c^3\ $ has no nonzero integer solutions? Suppose $\ a^3 + b^3 = c^3,\ a,b,c \in \mathbb Z^*,\ $then: $c^3 - b ^ 3 = (c - b)((c - b) ^ 2 + 3cb) = ...
3
votes
3answers
115 views

Does $x^2+x+1 \equiv 0 \pmod {997}$ have solutions? Why or why not?

I'm have difficulty solving this problem in my textbook. Does $x^2+x+1 \equiv 0\pmod{997}$ have solutions? Why or why not? I guess the first step would be $$ \begin{array}{l} (2x+1)^2 \equiv ...
0
votes
2answers
38 views

Let $p$ be an odd prime and $(a,p)=1$. Show that $x^2≡a$ (mod $p)$ has solutions, then $x^2≡a$ (mod $p^n)$ always has solution , for any $n>1$.

Let $p$ be an odd prime and $(a,p)=1$. Show that $x^2≡a$ (mod $p)$ has solutions, then $x^2≡a$ (mod $p^n)$ always has solution , for any $n>1$. I have solved the first part but second part need ...
0
votes
2answers
54 views

Let $p > 3$ be a prime number. Show that $x^2 \equiv −3\mod p$ is solvable iff $p\equiv 1\mod 6$.

Let $p > 3$ be a prime number. Show that $x^2 \equiv −3\mod p$ is solvable iff $p\equiv 1\mod 6$. My try is let $a$ be a solution of $x^2 \equiv -3 \mod p$. so $a^{p-1} \equiv 1\mod p$. This ...
2
votes
1answer
44 views

Primitive roots and quadratic nonresidues modulo a prime of form $2^n+1$ [duplicate]

Let $p$ be a prime number. We call a unit $a$ in $\Bbb Z/p\Bbb Z$ a primitive root, if $\text{ord}_p(a)=p-1$. Any unit in $\Bbb Z/p\Bbb Z$ can be written as some power as some power of $a$. if $p$ is ...
4
votes
0answers
89 views

Adding Numbers Pattern

A few nights ago I couldn't sleep and so started doing this: I would take a number and add up all of its digits to get a new number and then add up all of those digits and so on until there was only ...
1
vote
0answers
39 views

Which basis orders [for the natural numbers] have been proven?

The set $A$ of nonnegative integers is called an additive basis of order $h$ if every nonnegative integer can be written as the sum of $h$ not necessarily distinct elements of $A$. For example, the ...
0
votes
0answers
51 views

Proof of convergence of Kaprekar's Constant

I've tried googling this one a bit but nothing seems to come up, even though its considered to be a well known fact. Why does the kaprekar process of taking a 4 digit number: L, generating L' and L'' ...
1
vote
1answer
41 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
1
vote
0answers
39 views

variation of the Euler $\phi$ function?

Let $n \leq m$ be positive integers. Is there a function or expression giving the cardinality of the set $\{r \in \mathbb{Z}^+| 1 \leq r \leq m, \gcd(r,n) = 1 \}$? If $n = m$, it's just $\phi(n)$.
4
votes
1answer
86 views

Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as ...
1
vote
2answers
85 views

Proving the divisibility of large numbers without making large calculations [duplicate]

How would you you show that $2^{32}+1$ is divisible by $641$ without making large calculations?
3
votes
3answers
68 views

Prove that there exists $s$ such that $s(ab-1)^n +1$ is composite

I find this interesting question in a number theory book. Given two positive integers $a, b$ such that $a>1, b>1, \gcd(a, b)=1$. Prove that there exists a positive integer $s$ such that ...
1
vote
2answers
226 views

Solutions to the Mordell Equation modulo $p$

It is well known that the Mordell Equation $x^2 = y^3 + k$ has finitely many solutions, but has solutions modulo $n$ for all $n$. One proof of this involves using the Weil Bound to show that $x^2 = ...
1
vote
2answers
52 views

Help with proof regarding degrees of polynomials

How do you prove that if $f(x)\mid g(x)$ in $F[x]$, then either $g(x) = 0$ or $\deg(g(x)) \geq \deg(f(x))$ I'm not really sure how to prove these types of statements
2
votes
0answers
30 views

Polynomial Density Theorem

So I was consider Lagrange's 4-square theorem and came up with this generalization: Given a polynomial with rational coefficients $$P(x) = a_0 + a_1x + ... + a_nx^n$$ Determine if there exists ...