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

learn more… | top users | synonyms

6
votes
0answers
152 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
1
vote
1answer
28 views

Question about multiplication of modulars

Why is the property when you multiply two modulars (you multiply the two ones on outside and the two ones inside) Why does that property hold true? Addition is easy but multiplication doesn't make ...
0
votes
1answer
31 views

Congruence and modular arithmetic

$228,547,866$ divided by $q$ leaves the remainder of $r$. Find $r+q$. The problem is designated to be solved by using modular arithmetic. Even though I haven't learned what that is.
5
votes
3answers
232 views

Sums of squares question

If you have $a,b\in\mathbb{N}$ such that $a^2+b^2=M$, are there other natural numbers $c,d$ such that $c^2+d^2=M$? If so, is there an algorithm for generating such pairs or an equation relating them ...
1
vote
0answers
85 views

How to prove $\pi ^{3}$ is not constructible from the fact that $\pi $ is not constructible?

I know how to do this for $\sqrt[3]{\pi }$: First suppose it is constructible and then you just set it equal to $x_{0}=\sqrt[3]{\pi }$ and take the third power of both sides. Then you get ...
7
votes
1answer
134 views

Find all natural numbers such that $\sum_{k=1}^{n} \frac{n^k}{k!}$ is an integer

Find all natural numbers such that $\sum_{k=1}^{n} \frac{n^k}{k!}$ is an integer. I've tried to bring all fractions under commmon denominator and it didn't helped me much. With guessing I find out ...
0
votes
1answer
66 views

Let R = Z/4Z = {0, 1, 2, 3}. Find elements of R[x] which are neither units nor zero divisors.

I know that units are elements that are congruent to 1 modulo 4 when multiplied to some element in Z/4Z. I know that zero divisors are elements that are congruent to 0 modulo 4 when multiplied to some ...
1
vote
3answers
109 views

Proof that any square is of the form $3k$ or $3k+1$

Prove that the square of every natural number is of the form $3k$ or $3k+1$, where $k \in \mathbb{Z}$. I'm trying to reach a contradiction by assuming $n^2 = 3k+2$. Any ideas?
2
votes
1answer
48 views

consecutive prime power

I'm interesting on consecutive prime power numbers. I see that there is the Mersenne primes and the Fermat Primes that give solutions and $(8,9)$. In Sloane collection it is referred on A006549 and it ...
0
votes
0answers
45 views

Method for estimating euler phi without knowing the actual factors.

Is there any method to calculate Euler's totient function $\varphi$ without actually factorizing the number. Estimation of $\varphi$ or determining the range in which its value will lie for a given ...
1
vote
1answer
59 views

If p $\equiv$ 3 (mod 4) with p prime, prove -1 is a non-quadratic residue modulo p.

If p $\equiv$ 3 (mod 4) with p prime, prove -1 is a non-quadratic residue modulo p. I suppose this would not be true if p $\equiv$ 1 (modulo 4). To prove something is a non-square I find to be ...
0
votes
2answers
93 views

Solve and explain diophantine equation

A Diophantine equation ax+by = c always has a solution whenever a and b are relatively prime. Find x ,y such that $$93x-81y=3 $$
0
votes
3answers
155 views

Method of solving extended Euclidean algorithm for three numbers?

I already got idea of solving gcd with three numbers. But I am wondering how to solve the extended Euclidean algorithm with three, such as: 47x + 64y + 70z = 1 ...
4
votes
2answers
135 views

Why is the Legendre symbol not defined for $p = 2$ (even prime)?

Why is the Legendre symbol not defined for $p = 2$ (even prime) ? According to the definition of the Legendre symbol $$\left(\frac a p\right)$$ it is defined for an odd prime $p$ only. Even thus ...
1
vote
0answers
75 views

Proposition 17, p. 68 of Lang's Algebraic Number Theory

I'm stuck on a detail of the following propositon: Let $K, E$ be linearly disjoint number fields with degrees $n$ and $m$ over $\mathbb{Q}$ whose discriminants (over $\mathbb{Q}$) are relatively ...
13
votes
3answers
1k views

Infinity Hotel problem

Q. Welcome to the infinity hotel has an infinite number of rooms $1,2,3,4,...$ The manager notices all of the rooms have the lights on. He flips the switch every other one. (Rooms $2, 4, 6, …$) Then ...
0
votes
2answers
32 views

Induction question help.

Let $x$ and $y$ belong to a commutative ring $R$ with prime characteristic $p$. Show that, for all positive integers $n$ $$ (( x + y )^p)^n = (x^p)^n + (y^p)^n $$ I hope you can can understand ...
3
votes
2answers
50 views

Proof for the existence of primes not equal to $ap_\alpha +bp_\beta$ etc?

Is there a general proof to show that there exists prime numbers larger than $min(p_\alpha,p_\beta)$that are not equal to $ap_\alpha +bp_\beta$, given $p_\alpha,p_\beta\in\mathbb{P}-\left\{2\right\}$ ...
2
votes
0answers
60 views

Prove that the number of solutions of $a.x^m + b.y^n = c \mod p$ same as $ax^{m'} + by^{n'} =c \mod p$.

This is a question found in Ireland and Rosen's "A classical Introduction to Modern Number Theory", Ch4 Q22. The question was as follows. Q. Prove that the number of solutions (x,y) to the ...
-2
votes
2answers
46 views

divisibility by 3 question

How to show that $3|a(2a^2 + 7)$ where $a$ is an integer? I know this can be proved by mathematical induction.But im searching for an argument like thing to show this
4
votes
1answer
57 views

Confusing verse in “Axiomatic Set Theory” by Patrick Suppes

While searching for prime ordinals, I found this: Goldbach’s Hypothesis is that every even natural number > 2 is the sum of two prime numbers. On the basis of the obvious definition of prime ...
6
votes
2answers
80 views

Showing $2^{n_2} + 3^{n_3}+\cdots+9^{n_9}$ is dense in $\mathbb{R}^+$

I encountered this problem via a friend. He asked me to prove that $$ \left\{u: u= \sum_{k=2}^9 k^{n_k} \quad n_k \in \mathbb{Z} \right\}$$ is dense in $\mathbb{R}^+$. I was able to show that $0$ ...
1
vote
1answer
91 views

Number divides Least Common Multiple(LCM)

Given n and m find the smallest k such that: n divides LCM(m,k) ; m divides LCM(n,k) My Solution : If: (m==n) then k=1 Else: ...
1
vote
2answers
76 views

Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
1
vote
1answer
36 views

Smallest sample to produce n%

Q: A Statistic is published that 31% of people think it is okay to smoke in public. What is the smallest sample that could have been interviewed to get this result. A: 13, with 4 "yes" and 9 "no" ...
0
votes
1answer
39 views

quadratic residues and prime divisor

Prove that exist a many infinitely positive integers $n$ such that $n^2+1$ have a prime divisor greater than $2n + \sqrt{2n}$. I was trying to solve but without interesting advances. Any idea ...
0
votes
3answers
49 views

Divisibility proof by induction.

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
0
votes
1answer
47 views

Can one freely take the discrete logarithm of an element in a subset of a finite field?

Consider $\mathbb{F}_p^\times$ and $S = \{a \in \mathbb{F}_p^\times : a^n \equiv 1 \mod p\}$ for any $n$. Suppose I have $a \in S$. If I also have that $a^j \equiv a^k \mod p$, can I just take the ...
2
votes
3answers
87 views

On special integer gaps.

Calling an integer square-in if it is not square-free or a square. If $A$ and $B$ are two consecutive odd square-in integers , $A\gt B$ , let $A$ and $B$ is not a multiple of $9$ . Can $2\lt ...
2
votes
0answers
57 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
0
votes
0answers
48 views

quadratic residues and primes factors

Prove that if $(a,b)=1$ the number $a^2+b^2$ don't have prime factors of the form $4k-1$ and if also $(a,3)=1$ then the number $a^2+3b^2$ don't have factors of the form $3k-1$. We can say about the ...
0
votes
2answers
38 views

Let n be any positive integer. Find all primitive pythagorean triples which have 2^n as a side.

Q. Let n be any positive integer. Find all primitive pythagorean triples which have 2^n as a side. So here is what I have; We see that 2^n = 2∙2∙2∙∙∙2, n times, and is clearly an even number. Then ...
0
votes
3answers
39 views

How to show that if $24k+4$ and $24k+1$ are both perfect squares where $k$ is a natural number, then it is only when $k=0$?

I am trying to show that if $24k+4$ and $24k+1$ are both perfect squares where $k$ is a natural number, then the only possibility is when $k=0$. Here is how I did it: Let $24k+4=x^2$ and $24k+1=y^2$, ...
1
vote
3answers
565 views

Find the smallest positive integer x such that 2015! ≡ x (mod 2017)

Q. The next year that is a prime is 2017. Find the smallest positive integer x such that 2015! ≡ x (mod 2017). So, this is what I have; By Wilson’s theorem, (2017-1)! ≡ -1 (mod 2017) ⇒ 2016! ≡ -1 ...
1
vote
3answers
170 views

if GCD =LCM then prove a=b [closed]

Show that for $ a,b ∈ Z^+,\,$ if $[a,b]=(a,b),\,$ then $a=b$. Prove if GCD if a and b is equal to LCM of a AND b then $a=b$
18
votes
3answers
771 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
60
votes
12answers
15k views

Dividing 100% by 3 without any left

In mathematics, as far as I know, you can't divide 100% by 3 without having 0,1...% left. Imagine an apple which was cloned two times, so the other 2 are completely equal in 'quality'. The totality ...
3
votes
3answers
151 views

Prove that the equation $x^3 + 10000 = y^3$ has no solutions

The below question was given in my workbook for number theory. I have seen the solution, and it utilizes $\mod 7$, but I am unsure of why $\mod 7$ was chosen to solve the problem. Would any number of ...
-1
votes
2answers
84 views

Show the sum is equal to a product of six primes

On a set of math challenges, one of them is to prove that 145678+456781+567814+678145+781456+814567 is the product of six different primes. This sounds like number theory to me, but I have no ...
1
vote
1answer
41 views

Is every unit vector in $\mathbb{Q}^n$ the first column of a rational orthogonal matrix?

Equivalently, does every unit vector in $\mathbb{Q}^n$ belong to some orthonormal basis for $\mathbb{Q}^n$? This is clearly true for $\mathbb{Q}^2$, and for $\mathbb{Q}^3$ it seems to be true for ...
0
votes
1answer
73 views

Equivalent definitions of the quadratic gauss sum

In Ireland and Rosen, the quadratic Gauss sum of $a$, $g_a$, is defined by $g_a=\sum_{t=0}^{p-1}(\frac tp)\zeta^{at}$ with $\zeta$ a $p$th root of unity, $p$ an odd prime and $(\frac\cdot\cdot)$ the ...
0
votes
4answers
87 views

Ordering the solutions to Pell's Equation

Let $S$ be the set of positive integer pairs $(x,y)$ such that $x^2 - d y^2 = -4$ or $x^2 - d y^2 = 4$, where $d$ is fixed as the discriminant of a real quadratic number field. I'm trying to show ...
1
vote
2answers
190 views

Determine all complex numbers z in equation:

Let $n\in\mathbb{N}$. Determine all complex numbers $z\in\mathbb{C}$ such that $z^{n-1}$ = $\bar{z}$ How would I begin this? Would I begin by saying $z=a+ib$ and expand and stuff?
2
votes
2answers
50 views

Gaps between integers that are neither square-free nor a square

Call an integer square-in if it is not square-free or a square. Can two consecutive square-in numbers have a gap of $<8$ integers between them, exactly one of these integers in this 'gap' being a ...
0
votes
1answer
20 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
5
votes
1answer
65 views

Is there such $p$ that for all $q$, $4pq+2p+1$ isn't prime?

Is there such $p$ that for all $q$, $4pq+2p+1$ isn't prime? As $4pq+2p+1=2p(2q+1)+1$, I guess the problem can be restated as "is there such an even number, that its product with any odd number plus ...
0
votes
0answers
44 views

$\lim _{x \to \infty} \sum_{p\leq x, p \equiv 1(mod k)} \frac {log(p)}{p}= \infty $

Where can I find a proof of the following equation? $\lim _{x \to \infty}\sum_{p\leq x,p \equiv 1(mod k)} \frac {log(p)}{p}= \infty $ where p is prime. The proof should be as elementary as ...
3
votes
1answer
57 views

$Ord_n(ab)$ when $(a,n)=(b,n)=1$ but $(Ord_n(a), Ord_n(b))\neq 1$

What can be said about $Ord_n(ab)$ when $a,b$ are positive integers both relatively prime to $n$ and $Ord_n(a)$ is not relatively prime to $Ord_n(b)$? To start the proof I let $r=Ord_n(a)$, ...
2
votes
1answer
71 views

A proof for a (non-constant) polynomial can't take only primes as value

I know a proof of this statement, see How to demonstrate that there is no all-prime generating polynomial with rational cofficents? My question is that, in the book ...
3
votes
0answers
68 views

Josephus Variant

I set myself the challenge of trying to solve a variant of trying to solve a variant of the josephus problem where instead of killing every second person, every third person dies. The formula for the ...