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

learn more… | top users | synonyms (1)

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 ...
-1
votes
2answers
36 views

Prove that Carmichael number has no primitive roots

Prove that if $n$ is a Carmichael number, then $n$ has no primitive roots. This seems tricky to prove, and the only logical explanation for this is that it contradicts the basis of the Lucas Primality ...
1
vote
1answer
15 views

Proving $(n/p)$, a Legendre symbol, is multiplicative

Proof if $p|n$ or $p|m$ then $p|nm$, so $(n*m)/p=0=(n/p)(m/p)$ if p doesnt divide n then , $$(n*m/p)=(n*m)^{{p-1}/2}(mod \text{ } p)$$ $$(n*m/p)=n^{{p-1}/2}m^{{p-1}/2}(mod \text{ } p)$$ $$(n*m/...
0
votes
1answer
22 views

Question about proof of euler's criterion

When a is quadratic residue of the odd prime p, we arrived to the conclusion $(p-1)! \equiv -a^{{p-1}/2}\pmod{p}$. How does that imply $a^{{p-1}/2} \equiv 1\pmod{p}$
5
votes
5answers
158 views

Prime divides $n^2 + 1 \Rightarrow$ prime doesn't divide $n$

How can I show that if a prime $p$ divides $$n^2 + 1$$ then it doesn't divide $n$?
5
votes
2answers
64 views

Proving Wilson's theorem

Wilson's theorem: if $p$ is prime then $(p-1)! \equiv -1(mod$ $ p)$ Approach: $$(p-1)!=1*2*3*....*p-1$$ My teacher said in class that the gcd of every integer less than p and p is 1, so every ...
0
votes
2answers
84 views

What is a Diophantine equation, and why should we care about them? [closed]

As the question title suggests, what is a Diophantine equation, and why should a high schooler learning about elementary number theory care about them?
3
votes
1answer
25 views

What is the complete (polynomial) factorization of $\sigma(p^k)$, where $p$ is prime with $p \equiv k \equiv 1 \pmod 4$?

The title says it all. What is the complete (polynomial) factorization of $\sigma(p^k)$, where $p$ is prime with $p \equiv k \equiv 1 \pmod 4$? Here, $\sigma = \sigma_{1}$ is the classical sum-...
5
votes
0answers
42 views

Explaining difference between natural numbers, integers, rationals, reals, complex numbers, Gaussian integers [closed]

As so far as usage in elementary number theory goes, what is the difference between the natural numbers, the integers, the rational numbers, the complex numbers, and the Gaussian integers?
2
votes
2answers
39 views

Mills Test Running Time

Can Miller's Test be replaced with the bound below in hopes that it would make a faster general-purpose primality test (compared to ECPP). If $n$ is an $a$-SPRP for all primes $a$ $<$ ($\log_2 n$)...
4
votes
1answer
43 views

Intuition for basic fact surrounding Gaussian integers.

What is the intuition behind the following fact? Among the odd primes: Those that have remainder $3$ upon division by $4$ remain prime in $\mathbb{Z}[i]$. Those that leave remainder $1$ ...
20
votes
0answers
185 views

$x_1 = 2$, $x_{n + 1} = {{x_n(x_n + 1)}\over2}$, what can we say bout $x_n \text{ mod }2$?

Let$$x_1 = 2, \quad x_{n + 1} = {{x_n(x_n + 1)}\over2}.$$What can we say about the behavior of $x_n \text{ mod }2$? Is there an exact formula for $x_n \text{ mod }2$?
1
vote
1answer
47 views

Question from Number Theory Through Inquiry

I am having trouble proving the following theorem from the book Number Theory Through Inquiry: Let $p$ be a prime, $b$ an nonzero integer, and k a natural number. Then the number of $k$-th roots of $...
2
votes
2answers
55 views

Find all the numbers $n$ such that $3\cdot 2^n+2\cdot 3^n\equiv 1 \pmod 7$

Find all the numbers $n$ such that $3\cdot 2^n+2\cdot 3^n\equiv 1 \pmod 7$ Attempt: $\star$ denotes $3\cdot 2^n+2\cdot 3^n$ $$\text{for }n=1:\quad\star\equiv 5\not\equiv 1\\ \text{for }n=2:\quad\...
2
votes
3answers
79 views

There are infinitely many odd numbers not expressible as the sum of a prime number and a power of $2$

Prove that there are infinitely many odd integers that are not expressible as the sum of a prime number and a power of two. This is a difficult problem. Please give me some hints and some examples of ...
0
votes
3answers
206 views

Is it possible that $(\text{even}/\text{even})\times \text{even} = \text{odd}$? [closed]

Do even natural numbers $e_1,e_2,e_3$ exist with $\frac{e_1}{e_2}\cdot e_3=o$, such that $o$ is an odd natural number? Find a relation for these three even numbers $(e_1,e_2,e_3)$.
0
votes
1answer
28 views

Theorem on arithmetic of natural numbers.

From "Analysis I"-Herbert & Joachim: (starting from the Peano axioms) "There are operations addition + , multiplication · and a partial order ≤ on N which are uniquely determined by the ...
0
votes
2answers
53 views

Solve $a\equiv (105^{70}+1)^{15}\pmod {51}$

Find a number $a\in[0,50]$ such that $a\equiv (105^{70}+1)^{15}\pmod {51}$ My question is there a simple way to solve this by hand? maybe using Fermat's little theorem or something?, I tried this ...
6
votes
0answers
61 views

The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$

For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
25
votes
3answers
4k views

What is this operator called?

If $x \cdot 2 = x + x$ and $x \cdot 3 = x + x + x$ and $x^2 = x \cdot x$ and $x^3 = x \cdot x \cdot x$ Is there an operator $\oplus$ such that: $x \oplus 2 = x^x$ and $x \oplus 3 = {x^{x^x}}$? ...
1
vote
1answer
60 views

Prove that $390\mid n^{13}-n$ for all $n\in\mathbb Z$ [duplicate]

Prove that $390\mid n^{13}-n$ for all $n\in\mathbb Z$ Attempt: $$390=2\times3\times5\times13$$ Fermat theorem: $a^p\equiv a\pmod p$, here: $$n^{13}\equiv n \pmod{13}$$ So $\color{red}{13}\mid n^{...
0
votes
0answers
41 views

Is this reasoning of Chinese Remainder Theorem correct?

Originally I want to prove $y^{p'} \equiv x^n + C \pmod p$ is always having integer solution for some prime $p$ and $p'$ It is given by my classmate, so I do not know if it can really be proved, but ...
1
vote
3answers
36 views

Prove that if $p$ is a prime, then $p$ is a factor of $\binom{p}{r}$ for $r=1,2,\dots,p-1$ by using induction.

Prove that if $p$ is a prime, then $p$ is a factor of $\binom{p}{r}$ for $r=1,2,\dots,p-1$ by using induction. First, $\binom{p}{1}=p$. So it is clear that it has factor $p$. Suppose that $\binom{p}{...
1
vote
2answers
74 views

Are there any two identical terms in this series, defined parallely to the primes? [closed]

Let $p_n$ denote $n$-th prime number and $k_n$ be sequence that is \begin{align} k_1 &= 1 \\ k_2 &= p_2 - k_1 &&( 3-1 = 2 ) \\ k_n &= p_n - k_{n-1} &&\text{( n is integer ...
1
vote
2answers
43 views

Question about Lagrange's and factor theorem

Find all solutions $x^{12} \equiv 1 \pmod{13}$. Hint: the computation of high powers is better accomplished by using binary expansion of the exponent. Approach: This time I don't have a clear ...
5
votes
3answers
239 views

Number Theory GCD/LCM Problem

The following is from a problem set: Let $a,b,c$ be three positive integers such that $$\text{lcm}(a,b) \cdot \text{lcm}(b,c) \cdot \text{lcm}(c,a) = a \cdot b \cdot c \cdot \gcd(a,b,c). $$ ...
0
votes
3answers
51 views

Show that for all $a\in\mathbb{N}$, there exists $b\in\mathbb{N}$ and square-free integer $c$ such that $\sqrt{a}=b\sqrt{c}$.

I'm having some difficulties continuing this problem. I get that $b^2\mid a$ and $c\mid a$ but I am not sure where to go from there.
1
vote
3answers
39 views

Solution to Divisibility Problem

I have attempted to solve problem which is stated as follows: $2^n+1=xy$ where $n>0$ and $x,y>1$. Prove that $2^a$ divides $x-1$ iff $2^a$ divides $y-1$. My solution is as follows: $x$ ...
3
votes
2answers
16 views

Prove that $a \mid k$ if $a \mid k·c$, $a \mid k·b$ and $gcd(c,b)=1$ for all $a,b,c,k \in \mathbb{Z}$ [closed]

Let $a,b,c,k \in \mathbb{Z}$ and $a \mid k·c$, $a \mid k·b$ and $gcd(c,b)=1$. Prove that $a \mid k$.
1
vote
0answers
44 views

A more sophisticated method of finding all $n$ satisfying $n! = (k + 1)(k-1)$?

Find all $n$ such that $n!$ can be expressed in the form $(k+1)(k-1)$ where $k$ is an integer $>1$. This problem stems from another problem that I tried to solve from David Burton's number theory ...
4
votes
1answer
47 views

Question about oblique co-ordinate system

Definitions: Let the following figure show an oblique $2$ dimensional co-ordinate system, where $O$ is the origin and the parallelogram $OQRP$ is called the fundamental parallelogram. Rest of the ...
0
votes
1answer
22 views

Hypothetical equation (modulo a power of two) and the value [duplicate]

We have hypothetical equation: $2^{b} \% k = z$. Assume that we know $z$, $b$ and $k$. So everything! We want to know only if the above equation is true. I do not want to use the exponentiation ...
6
votes
2answers
384 views

Existence of the natural density of the strictly-increasing sequence of positive integer?

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{A(n)}{n}$ whenever the limit ...
1
vote
0answers
37 views

How to provide Mathematical Proof for number theory scheme?

I have a set S={1,2,...,N-1}. N=pq (where p and q are RSA prime numbers). Scenario is that User need to retrieve the Database blocks without revealing his block index to the Server i.e, Private ...
0
votes
1answer
31 views

Checking proof of simple number theory problem

I came up with a solution to a number theory problem. Please check it. Prove that $a^2 + b^2 + c^2 + d^2$ is never a prime if $ad=bc$, where $a,b,c,d$ are positive integers. We will prove the more ...
2
votes
1answer
48 views

Proof about Lagrange's theorem in number theory

Based on the textbook Lagrange's theorem states: The congruence $$f(x) \equiv 0\pmod p$$ in which $$f(x)=a_0x^n+....+a_n,\text{ } a_0\not\equiv0\pmod p$$ has at most $n$ roots. $p$ is a prime number ...
5
votes
2answers
121 views

Properties of a finite field extension of degree 2.

I am bad (but trying to improve!) at very basic number theory and algebra. I'm quite sure this question is easy, but I do not know what fundamentals I am missing. This is from Ireland & Rosen's "...
0
votes
1answer
41 views

Question about Lagrange's theorem

Based on the textbook Lagrange's theorem states: The congruence $$f(x) \equiv 0(mod\text{ } p)$$ in which $$f(x)=a_0x^n+....+a_n,\text{ } a_0\not\equiv0(mod\text{ } p)$$ has at most n roots. p is a ...
0
votes
1answer
24 views

Help proving generalized Miller-Rabin Test

Please help me prove the following theorem below based off of Fermat's Little Theorem: If $p$ is prime, and $a^{(p-1)/q}$ $=$ $x$ $\pmod p$ where $q$ is a proper divisor of $p-1$ then, $x^q$ $=$ $...
1
vote
2answers
63 views

Numbers $a$ such that if $a \mid b^2$ then $a \mid b$

I want to describe the set of numbers $a$ such that if $a \mid b^2$ then $a | b$ for all positive integers b using the prime factorizations of $a$ and $b$. What would be a good way to approach this ...
4
votes
1answer
61 views

A number which can be factored into a product of $k$ and $k+2$ consecutive natural numbers (each $>1$)

We say that the number $N \in \mathbb{N}$ has the property $P(k)$ if it can be factored into a product of $k$ consecutive natural numbers (not equal to $1$). Find the value of $k$ such that some $...
0
votes
0answers
22 views

Question about polynomial congruences

$x^3 \equiv x(mod$ $ 3)$ for all x, whereas obviously $x^3$ and $x$ are not algebraically congruent $(mod$ $ 3)$. What does it mean to be algebraically congruent?. In this case the two polynomials can ...
2
votes
0answers
44 views

Induction Implies Well Ordering

Every proof that induction implies well ordering I have seen goes: assume $S\subset\mathbb{N}$ has no least element and let $T$ be its complement with respect to $\mathbb{N}$. Since $1$ is the ...
6
votes
4answers
423 views

General solution of Pell's equation

If we know the minimal solution or any specific solution of Pell's equation $x^2-ny^2=1$ , is there is any general formula to write all solution of Pell's equation?
0
votes
1answer
54 views

Prove that we cannot found any simple algebraic sloution for $n>2$

for this sequance we can write this formula:$\{1-1,1,-1,1,-1,1,...\}=(-1)^n$ for this also we can do that: $\{-1,-1,1,1,-1,-1,1,1,-1,-1,...\}=(-1)^\frac{n(n+1)}{2}$ But how to prone there is no ...
1
vote
1answer
62 views

Find all the numbers $n$ such that $\varphi(n)=5$

Find all the numbers $n$ such that $\varphi(n)=5$ Attempt: $$n=\prod\limits_{i=1}^{k} p_i^{\beta_i}$$ $$\varphi(n)=\prod\limits_{i=1}^{k}p^{\beta_i-1}(p-1)$$ We need: $$\prod\limits_{i=1}^{k}p^{\...
0
votes
0answers
27 views

Number Theory and p-Power-Partitioned Numbers

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, we're going to define its digits-partition as the set $D_{N} = \bigcup_{j=1}^{n}\bigcup_{k=1}^{p(a_{j})}\{(P_{k},j)\}$, where each pair $(P_{k},...
1
vote
1answer
36 views

How you know where to use LCM (Least Common Multiple)

I'm new in number theory and my question might be very simple for you, but I don't understand how you know when to use LCM. For example in this question: Mike and Sara work together and Sara takes a ...
2
votes
1answer
46 views

Number of vectors whose sum of components multiplied by position is a constant

Given $n \in \mathbb{N}$, I am interested in the vectors $(v_1, \dots, v_m)$ with $v_i \in \mathbb{N}$ for $1\leq i \leq m$, such as the linear diophantine equation: $$ \sum_{i=1}^{m} iv_i = n $$ ...
3
votes
3answers
94 views

Find the Prime Factorization of $\varphi(11!)$

Find the Prime Factorization of $\varphi(11!)$ What I did: $\varphi(11!)=\varphi(11)\cdot\varphi(10)...\varphi(1)$ $$\varphi(11)=2\cdot 5\\ \varphi(10)=2^2\\ \varphi(9)=3\cdot 2\\ \varphi(8)=2^2\\ ...