0
votes
0answers
28 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
39 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
26 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
83 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
69 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
66 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
204 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 = ...
0
votes
1answer
50 views

fastest algorithm for prime factorization [on hold]

I need the fastest algorithm to factorize the given number $N$ as a product of primes. $$N=p_1^{e_1}p_2{e_2}\ldots p_n^{e_n}$$ where $p_1, p_2,\ldots ,p_n$ are primes and $e_1,e_2,\ldots, e_n$ are ...
1
vote
2answers
46 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
-1
votes
0answers
40 views

How does this method work? [closed]

Let $n=16$ for an example: step 1: get set of prims from $1$ to $\sqrt{2n}: \{2, 3, 5\}$, step 2: get set of $n \mod 2, n \mod 3, n \mod 5: \{0, 1, 1\}$, setp 3: from $0$ to $n-3$, ...
2
votes
0answers
27 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 ...
0
votes
0answers
22 views

Fermat pseudoprimes p to base 2 (AKA Sarrus or Poulet numbers) with special properties

Are there any known Fermat pseudoprimes $p\;$ to base $2\;$ (Sarrus or Poulet numbers) with the properties $q = (p-1)/2\;$ is prime and $p \equiv 0 \pmod 3?$ I was not able to find any example up to ...
1
vote
0answers
51 views

Finding the number of elements in $\left(ℤ[i]\right)_m$

If $m$ = $m_1$ + $m_1i$ ∈ $ℤ[i]$, is there a general formula to find the number of elements in $\left(ℤ[i]\right)_m$?
0
votes
0answers
24 views

What are the patterns in the number of divisors $d(n)$ of the highly composite numbers?

I am trying to understand the patterns in the number of divisors $d(n)$ of the highly composite numbers. The numbers marked with an asterisk are the superior highly composite numbers. The first ...
0
votes
1answer
40 views

Find $x$ such that $o_1^x-o_2^x \neq 2(o_3^x-o_4^x)$ where $o_i$ is an odd number, $o_1>o_2$, $o_3>o_4$ and $x$ is a positive integer

A few hours ago I asked this question. This problem came up while working on a graph labeling problem. I already have a exponential algorithm working. But I want to further reduce the complexity. ...
0
votes
2answers
42 views

Number theory proof regarding congruences and common divisors

Anyone know how to prove the following statement? If $ a=b $ (mod m) then the common divisors of a,m are the same as those of b,m
0
votes
0answers
22 views

Given an integer n find smallest integer i such that σ(i)=n. Smallest Inverse Sum of Divisors

Hi All I need some help I am trying to solve this problem which involves computation of sum of divisors and its inverse. In other words Given an integer n find smallest integer i such that σ(i)=n ...
0
votes
1answer
41 views

Number theory proof regarding norms

How would you prove that if $x$ is a prime in $ℤ[i] \Longleftrightarrow$ $N(x)$ is a prime in $ℤ$ N(x) represents the norm of x.
0
votes
2answers
46 views

Number theory proofs regarding units and orders

Hey I just came across this proof but I have no idea how to prove this. If $u$ ∈ $U_m$ has order $n$ and ($k,n$) = 1, then $u^k$ has order n. Any ideas?
1
vote
0answers
21 views

Elementary Application of Legendre Symbol [duplicate]

For odd primes $p,q$ with $p\equiv q\pmod{4a}$, then how can we show that $a$ is a quadratic residue $\mod p$ if and only if it is a quadratic residue $\mod q$ using legendre/jacobi symbols?
2
votes
1answer
49 views

need help in number theory problem

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
1
vote
1answer
57 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
-1
votes
1answer
36 views

Who will be last [closed]

There are n children in school and teacher is going to give some candies to them. Let's number all the children from 1 to n. The i-th child wants to get at least a[i] candies. Teacher asks children ...
1
vote
1answer
54 views

factoring polynomials in $\Bbb Z/11\Bbb Z$

Any ideas as in how to Factor $x^{10}-1$ into linear factors in the integers modulo $11$, $\Bbb Z_{11}=\Bbb Z/11\Bbb Z$? I've been trying but can't come up with an answer.
0
votes
0answers
19 views

Complete residue mod $p$ and number of solution to an equation

Prove that there are infinitely many primes $p$ such that the total number of solutions $\pmod{p}$ to the equation $3x^{3}+4y^{4}+5z^{3}-y^{4}z \equiv 0$ is $p^2$. I can show that for $p \equiv ...
7
votes
2answers
258 views

Is $7^{8}+8^{9}+9^{7}+1$ a prime? (no computer usage allowed)

Prove or disprove that $$7^{8}+8^{9}+9^{7}+1$$ is a prime number, without using a computer. I tried to transform $n^{n+1}+(n+1)^{n+2}+(n+2)^{n}+1$, unsuccessfully, no useful conclusion.
1
vote
2answers
85 views

number theory proof regarding number of roots

I was given this proposition but I was never able to prove it. Does anyone know how to solve this? if f is a polynomial in $\Bbb Z_p\left[x\right]$ and the deg(f) = n then f can have at most n roots. ...
0
votes
1answer
61 views

number theory proofs with units, orders, and the phi function

How do you prove the following? : There is an element $u_0$ of $U_m$ whose order is divisible by the order of every other element of $U_m$. If the order of $u_0$ is n then the polynomial $x^{n-1}$ ...
1
vote
3answers
68 views

Number theory proofs relating to divisors [closed]

How do you prove this? $$\left(n-1\right)^2\mid\left(n^k-1\right)\Longleftrightarrow\left(n-1\right)\mid k$$
1
vote
0answers
46 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
1
vote
1answer
55 views

Number theory proofs relating to GCD's [duplicate]

$\left(a^n-1,a^m-1\right)=a^{\left(n,m\right)}-1$ for positive integers a,n,m where (a,b) stands for the GCD of a and b How do you prove this?
4
votes
2answers
52 views

An exercise in number theory: euclidean domain

I have an exercise for you about euclidean domain. Which primes $p<30$ in $\mathbb{Z}$ is a prime in $ \mathbb{Z} \left[ \frac{1+\sqrt{-7}}{2} \right] $ ? Thank you very much for the support, I ...
0
votes
1answer
185 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
3
votes
1answer
47 views

squares that can be divided to two squares

There are some squares like 169 that can be divided into two squares(16 and 9). I classify them into two groups: A:squares that their rightmost number isn't 0(like 169 and 4225) B:squares that their ...
0
votes
2answers
49 views

How to find irrational approximates

Say I have a rational number, $n$, that approximates an irrational number of the form: $$n \approx {a+\sqrt b \over c}$$ in terms of being irrational. What is a good way of finding the unknown ...
-1
votes
0answers
58 views

Sum of possible permutations

Lets call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x. For two ...
1
vote
1answer
50 views

Other Interesting solutions to $a=bq+r$? [closed]

The division algorithm says $a=bq+r$, with $r$ between $0$ and $b$. Are there interesting restrictions on $r$ using number-theoretic properties that make the equation $a=bq+r$ hold, or hold with ...
2
votes
1answer
90 views

Solutions to a diophantine equation

I tried to find integer solutions to the following diophantine equation $$x^3 - 3y^3 + 5z^3 - 3xy^2 + 3x^2y + 9xz^2 + 7x^2z + 3yz^2 - 3y^2z + xyz = 0$$ but was unable to do so. I suspect that there ...
2
votes
1answer
52 views

Understanding Hensel's Lemma

I am learning Hensel's Lemma and trying to solve the polynomial congruence $$x^5+x^4+1\equiv 0\pmod{81}$$ Now my professor taught us the technique of building up from $p$, to $p^2$, and continuing to ...
1
vote
2answers
33 views

An exercise in number theory: associates elements

I have a question for you about associates elements in an integral domain. Let $R$ be an integral domain and define $aR := \{ ar \; | \; r \in R\}$. In the following, for $unity$ (denoted with $u$) I ...
0
votes
0answers
29 views

Differential Diophantine Equations?

So this is both a question on its own as well as a request for where I can find information on a given topic. Consider Differential Equations in two variables of the form: $$P(Z,Z', Z'' ... Z^{[n]}, ...
2
votes
1answer
31 views

The number of distinct multiples of composites greater than $n$ that can be factored into two naturals less than or equal to $n$

Given a list of composites between $n$ and $\lfloor \frac{n^2}{2} \rfloor$: What would be the most efficient way to count, for each composite, the number of its distinct multiples that can be ...
2
votes
0answers
48 views

Prove $a^m\equiv a^{m-\phi(m)}\pmod m$ for all positive integers

Prove that if $a,m$ are positive integers, then $$a^m\equiv a^{m-\phi(m)}\pmod m.\tag 1$$ If gcd$(a,m)=1$ then this is Euler's theorem. Denote gcd$(a,m)=k$ and $a=xk,m=yk$ then we need to prove ...
0
votes
0answers
21 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
4
votes
3answers
100 views

Elementary, direct proof of when $5$ is a quadratic residue mod $p$

$\newcommand{\kron}[2]{\left( \frac{#1}{#2} \right)}$ It's easy to use Quadratic Reciprocity to show that $\kron{5}{p} = \kron{p}{5} = 1$ when $p \equiv \pm 1 \pmod 5$, and is $-1$ when $p \equiv \pm ...
0
votes
1answer
151 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
0
votes
0answers
92 views

Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by: $$ \ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1. $$ For all terms of $A$ greater than $\ ...
0
votes
1answer
39 views

a finite induction question from burton's elementary number theory

this question comes from burton's elementary number theory, 4th edition. question 3 in 1.1 says to use the second principle of finite induction to establish that $$for\ all\ n\ge1,\ ^{(a)}\ ...
2
votes
2answers
67 views

Divisor Pattern - Number Theory

List all positive divisors of $18 $ List all positive divisors of $75 $ Find another number with the same number of divisors. What is the pattern? $18 – 1,2,3,6,9,18 $ $75 – 1,3,5,25,75 $ $99 – ...
2
votes
1answer
74 views

Infinite families of prime numbers

What interesting/useful infinite families of prime numbers are there? Right now it would be useful if I could find one with arbitrarily many 1's in its binary representation, but I am doing a larger ...