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

learn more… | top users | synonyms

1
vote
0answers
3 views

Rational vs irrational

If two points on a number line is shown, are rational numbers between the two points is more or irrational number is more ? I have tried using probability , my collegue who was like my teacher also ...
2
votes
1answer
31 views

Finding all primes $(p,q)$ for perfect squares.

Find all prime pairs $(p,q)$ such that $2p-1, 2q-1, 2pq-1$ are all perfect squares. Source: St.Petersburg Olympiad 2011 I have only found the pair $(5,5)$ so I am thinking that maybe a modulo $5$ ...
2
votes
4answers
123 views

Why irrational implies having an infinite decimal expansion?

Why irrational means having an infinite decimal expansion?
0
votes
1answer
19 views

Number Theory Prime Factor Problem

There is an integer N that has 12 factors, including 1 and itself, but only 3 of them are prime factors. The sum of these three prime factors is 20. What is the smallest possible value for N?
1
vote
2answers
59 views

Last Two Digits Problem

I'm trying to find the last two digits of ${2012}^{2012}$. I know you can use (mod 100) to find them, but I'm not quite sure how to apply this. Can someone please explain it?
1
vote
1answer
20 views

Is a Mersenne prime always of the form $4n + 3$?

Is a Mersenne prime always of the form $4n + 3$? Examples: $M_3 = 7 = 4 \times 1 + 3$ $M_5 = 31 = 4 \times 7 + 3$ $M_7 = 127 = 4 \times 31 + 3$ $M_{13} = 8191 = 4 \times 2047 + 3$ ...
1
vote
0answers
28 views

Quadratic reciprocity problem

How can I use quadratic reciprocity to prove that $-3$ is a quadratic residue $\pmod p$ if and only if $p=2$ or $p \equiv 1 \pmod 6$ and deduce that $\mathbb{Z}[\sqrt{-3}]/(p)\cong \mathbb{F}_p ...
3
votes
1answer
36 views

Show: $\varphi\colon\mathbb{Z}_{mn}\to\mathbb{Z}_m\times\mathbb{Z}_n, k\mapsto (k\% m,k\% n)$ is a ring isomorphism for $m$ and $n$ relatively prim

Let $m\in\mathbb{Z}, n\in\mathbb{N}$. Then there exist unique elements $q\in\mathbb{Z}, r\in\mathbb{N}$ with $0\leq r<n$ and $m=qn+r$. We write $r:=m\% n$. Let $m,n\in\mathbb{N}$ be relatively ...
3
votes
3answers
78 views

Proving that $a^n+b^n+c^n=0 \implies abc=0$.

Show that if $a^n+b^n+c^n=0$ with $a,b,c\in\mathbb{Q}$ and $n\ge 3$, then $abc=0$. By letting $a=a_1/a_2$ and so on I think I have shown it is sufficient to prove it for $a,b,c\in\mathbb{Z}$, but ...
0
votes
0answers
20 views

Euler-fermat theorem with huge exponents

we have just been taught the Euler-Fermat theorem and in the classwork the usual exercises are like "find the last $n$ digits of $a^{a^{b^{...^{z}}}}$ where $a,b,...,z$ are integers". The thing is ...
0
votes
0answers
12 views

Solving Legendre symbol in a different way [on hold]

One way of solving the Legendre symbol is by using quadratic reciprocity. I was wondering if there is another way to do this? (Of course, not the brute-force method of trying all possible x from 1 ...
2
votes
1answer
58 views

If $x_1^3+x_2^3+\ldots+x_t^3=2002^{2002}$, find minimum value of $t$ such that the predefined condition is satisfied for all natural numbers $x_i$'s

If $x_1^3+x_2^3+\ldots+x_t^3=2002^{2002}$, find the minimum value of $t$ such that the predefined condition is satisfied for all natural number $x_is$. My attempt: I took modulo $9$ on both sides ...
0
votes
2answers
38 views

Feedback on Euclidean Algorithm: $gcd(277, 301)$

Ans: $301 =277 \cdot 1 + 24$ $277 =24 \cdot 11 + 13$ $24 = 13 \cdot 1 + 11$ $13 = 11 \cdot 1 + 2$ $11 = 2 \cdot 5 + 1$ $2 = 1 \cdot 2 + 0$ Is this correct?
0
votes
3answers
32 views

Number Theory Remainder Question

I'm trying to find the answer to the following: What is the remainder when 9^2012 is divided by 11? Apparently, you're supposed to use Fermat's Little Theorem, but I'm not sure how to use it to solve ...
0
votes
2answers
80 views

Maximum among $1, 2^{1/2}, 3^{1/3}, 4^{1/4},…$

What is maximum value among $1, 2^{1/2}, 3^{1/3}, 4^{1/4},....$ ? My approach: let $f(x)=x^{1/x}$ then I found out the derivative of $f$. Since $f(x)$ is maximum where $f'(x)=0$ and $f''(x)<0$ ...
0
votes
1answer
19 views

Equation with a sum for the prime-counting function involving the Mobius function

I have come across the statement that $$ \sum_{n\leq x}\sum_{d\mid(n,P_z)}\mu(d) = \sum_{d\mid P_z}\mu(d) \left[\frac{x}{d}\right], $$ where $P_z=\prod_{p\leq z}p$ where $p$ is prime, $\mu(d)$ is the ...
4
votes
0answers
35 views

Applications of generating functions to number theory

I am familiar (at least at a cursory level) with the extensive role generating functions play in the theory of partitions. What are some other prominent applications of generating functions to number ...
0
votes
0answers
18 views

Find the highest LCM for n numbers in a range

I'm designing a component that takes a clock in (i.e. a periodic signal), and outputs a periodic signal with a lower frequency. To do so, I use two counters of different sizes. Here's an example, with ...
1
vote
2answers
39 views

Probability of number formed from dice rolls being multiple of 8

A fair 6-sided die is tossed 8 times. The sequence of 8 results is recorded to form an 8-digit number. For example if the tosses give {3, 5, 4, 2, 1, 1, 6, 5}, the resultant number is $35421165$. ...
2
votes
1answer
51 views

Lower bound on divisors of $\Phi_n(n) $

Take the nth cyclotomic polynomial $\Phi_n(x)$ and let $\phi$ be the Euler totient function. I can prove that all divisors $d$ of $\Phi_n(n)$ are such that $d \ge \phi(n)$ or $d = 1$. The proof is ...
0
votes
1answer
33 views

Solving diophatine equation of form $x^2+y^2=25$

How would you solve diophatine equations of the form $x^2+y^2=25$? I know how to solve linear diophatine equations but I have not done any of quadratic form before. I could use trial and error because ...
1
vote
0answers
44 views

Is this theorem provable using relatively elementary number theory and abstract algebra?

$\textbf{Theorem}$: Let $p$ be a prime. Let $q$ be a prime that doesn't divide $p - 1$, so that $\mathbb{F}_p$ does have an element of order $q$. Let $\zeta$ be an imaginary number whose order is $q$. ...
1
vote
1answer
46 views

Solve a system of diophantine equations

I have a problem with elemental number theory. I started with the expression $$ (a - \frac{1}{b})(b - \frac{1}{c})(c - \frac{1}{a}) $$ and task to find all natural $a,b,c$ so that the result of the ...
0
votes
0answers
18 views

Expansion of $1/n$ in a different base $b$.

Let $(n,b)=1$. The decimal expansion of $\frac{1}{n}$ has period $n-1$ if and only if $b$ is a primitive root of $n$ and $n$ is prime. I'm having problems trying to prove the forward direction. ...
3
votes
0answers
37 views

Formula to round up to the next multiple not divisible by $2$ or $3$?

I want a formula that rounds up any integer to the next multiple of a given prime, which is not divisible by $2$ or $3$, so it is either $p$ or $5p \pmod{6p}$. The simplest formula is preferred. I've ...
10
votes
0answers
89 views

Curious number theory problem

$k,m,n\in\mathbb{N}$ satisfy $k^{m+n}=nm^n$. How can I show that $m=k$ and $n=k^k?$
1
vote
0answers
16 views

Show that the solutions lifted by Hensel's lemma, are the only solutions in $\mathbb{Z} / p^k \mathbb{Z}$

Suppose that $f(x) \in \mathbb{Z}[X]$ is a polynomial to which we can apply Hensel's Lemma. Suppose the set $A$ is the set of solutions of $f(x)$ in $\mathbb{Z} / p \mathbb{Z}$. I'd like to show that ...
1
vote
1answer
122 views

Consider the number $n= 2^{10^{33}} +1$ [on hold]

Consider the number $$n= 2^{10^{33}}+1$$ Suppose that it is known that none of the numbers $1 < k < 10^{6}$ divide $n$. Does it follow that n is a prime number? I know that the answer is a ...
2
votes
1answer
27 views

ON types of squarefree numbers and comparing their amounts < a given integer N.

Let an m-prime be a square-free number with m prime divisors. Also let the number of t-primes < N be represented as #(t-prime){N} (t and N being positive elements of integers). Is the following ...
-2
votes
0answers
14 views

what is a divisibility test for the number 6 in a base-twelve system? Justify it? [on hold]

I need a divisibility test for the number 6 in a base 12 system please help!
1
vote
1answer
24 views

Using trial division in $\mathbb{Z}/2\mathbb{Z}[x]$, factor $x^6+x^4+x$ into a product of irreducible polynomials.

I know how to normally factor this, but I am hazy on the idea of irreducible polynomials. I know that $x^6+x^4+x=x(x^5+x^3+1)$ but I am not sure how to tell if the second factor is irreducible, or if ...
0
votes
2answers
40 views

Let $f(x)=x^2+bx+4$ in $\mathbb{R}[x]$. For each $b \in \mathbb{R}$, factor $f(x)$ into a product of irreducible polynomials in $\mathbb{R}[x]$.

I know that for a polynomial to be irreducible, this means that if it is factored then one of the factors has to be a unit. I am confused by what this question is asking because there are an infinite ...
0
votes
1answer
18 views

Show that in Z/2Z[x] two polynomials are associates if and only if they are equal.

I believe that I should show the forward direction by first showing the factorization of two polynomials, f and g, such that f=p1 . . . ps and g=q1 . . . qs, where each pi and qj are irreducible ...
0
votes
1answer
30 views

Prove that $a^4 \equiv 1 \bmod 5$ if $\space a \neq 5$

Prove that $a^4 \equiv 1 \bmod 5$ if$ \space a \neq 5$ I've tried showing this by induction. Clearly if $ a = 5$ then $ a \equiv 0 \bmod 5$ now if $a = 1$ then $a^4 - 1 = 0$ which is divisible by ...
6
votes
2answers
106 views

What is the integral $\int x^t/\Gamma(1+t) \, dt$? (In general: relation between series and integrals)

(The question arises from playing with translating series into integrals) I wanted to see, what it means to have a "continuous" relative for powerseries and other series; the most simple one ...
1
vote
4answers
86 views

If $d=\gcd(a+b,a^2+b^2)$, with $\gcd(a,b)=1$, then $d=1$ or $2$

Suppose $\gcd(a,b)=1$. Let $d=\gcd(a+b,a^2+b^2)$. I want to prove that $d$ equals $1$ or $2$. I get that $d\mid2ab$ but I can't find a linear combination that will give me some help to use the fact ...
1
vote
2answers
51 views

Power of primes

We have proved that if $a > 3$, then $a$, $a+ 2$, and $a+ 4$ cannot be all primes in previous question. Can we say that they all be powers of primes?
4
votes
3answers
562 views

Proof about prime numbers

Can we prove that every prime larger than 3 gives a remainder of 1 or 5(edited) if divided by 6 and if so, which formulas can be used while proving?
3
votes
0answers
60 views

diophantine equation $ |x^2-py^2|=\frac{p-1}{2} $

Prime $p\equiv3\pmod4$, then the equation $$ |x^2-py^2|=\frac{p-1}{2} $$ has a solution in integers obviuosly, en, $x^2-py^2=-1$ has no solution in integers. Thanks a lot!
1
vote
0answers
30 views

Finding Mod Value [duplicate]

I have a problem in finding the solution of the equation given in the form of:$$153^{197}=x \mod 497$$ Can anyone hep me to solve this question?
1
vote
2answers
41 views

Why does the extended euclidean algorithm allow you to find modular inverse?

Why is it that by working backwards from the euclidean algorithm one can find the modular inverse of a number? Further, there is also another method for finding inverses discussed here which seems ...
-1
votes
0answers
14 views

What are the applications of quadratic residues?

I have covered the proofs of the laws of quadratic reciprocity (the Legendre and Jacobi symbols). However this treatment of quadratic residues has been pretty dry. Are there any real life applications ...
1
vote
0answers
33 views

About primes and counting them. [on hold]

Are there bounds to the prime counting function that do not involve logarithms? Considering the best bounds use logarithms why is the natural logarithm so closely related to the prime counting ...
5
votes
1answer
59 views

Problems that are made easy by using p-adic numbers

Does anybody know of elementary problems that can be be solved using the p-adics? Solutions are preferred.
4
votes
4answers
348 views

Is the reasoning/algebra for my proof correct? (musical tuning theory proof)

This isn't for a class, I was just wondering if I would be able to work out a proof for something like this myself for fun, and wanted to verify that my methods are correct. Basically, what I'm trying ...
1
vote
1answer
43 views

Integer solutions of the equation $a^{n+1}-(a+1)^n = 2001 $

I am doing number theory and I came across that question $a^{n+1}-(a+1)^n = 2001 $. Find the integer solutions and show that they are the only solution. I really tried hard but i am nowhere near ...
5
votes
1answer
77 views

For $n\ge4$, prove that $1!+2!+\cdots+n!$ cannot be the square of a positive integer

I'm trying to prove this by induction but seem to be getting nowhere.
7
votes
2answers
100 views

$a^3+3a^2+a$ is never a perfect square.

Prove that no number of the form $ a^3+3a^2+a $, for a positive integer $a$, is a perfect square. This problem was published in the Italian national competition (Cesenatico 1991). I've been ...
1
vote
1answer
30 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
1
vote
0answers
37 views

Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F} $

Is there a map between the group of $\mathbb{Z}_{N^2}^*$ where $N$ is a composite number , a product of two equal size secure prime numbers $p$ and $q$ and a finite field $\mathbb{F}$, such that for ...