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

learn more… | top users | synonyms

0
votes
0answers
37 views

If $k\le n$ and $k$ is relatively prime to $n$, there exists a prime $p$ such that $p \equiv k \mod n$.

I need to use this result in a step of a proof, but I am for some reason unable to justify it. It seems to be true, after trying some examples, but I am not sure why. If $1 \le k\le n$ and $k$ is ...
0
votes
1answer
40 views

Is there name to the following sequence: $c_n = c_1c_2…c_{n-1} + 1$

I just saw the sequence $c_n = c_0c_1c_2...c_{n-1} + 1$ and is thinking whether sequence $(c_n)$ has some name. Add: What if $c_0 \neq 2$?
0
votes
1answer
20 views

If $a\equiv b [p^k]$ then $a^p \equiv b^p [p^{k+1}]$

Can anyone explain the steps to this proof? I'm really lost/ If $k\geq 1$ and $a\equiv b[p^k]$ then $a^p \equiv b^p [p^{k+1}]$ Proof: Since $a= b + qp^k$ for some $q\in \mathbb{Z}$ we have $a^p = ...
1
vote
3answers
88 views

Product of “reversed” numbers

Consider any 2 binary numbers, e.g.: 10101011 ; 11111101 and their product, say P. "Reverse" (mirror image) all the digits of the 2 numbers, e.g.: ...
5
votes
1answer
58 views

Show that $3^n-2^n\cdot 5$ is composite for infinitely many $n$

I came across this problem: Show that $3^n-2^n\cdot 5$ is composite for infinitely many $n$ and do not know how to solve it. I only know that it is true for $n=7$, since then $1547=17\cdot 91$.
-1
votes
1answer
24 views

How to determine the integers $n$ for which $Z_n$, the set of integers modulo $n$, contains elements $x$, $y$ so that $x + y = 2,2x-3y = 3$.

How to determine the integers $n$ for which $Z_n$, the set of integers modulo $n$, contains elements $x$, $y$ so that $x + y = 2$ ; $2x-3y = 3$.
1
vote
1answer
54 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 ...
6
votes
4answers
188 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
3answers
281 views

Why irrational implies having an infinite decimal expansion?

Why irrational means having an infinite decimal expansion?
0
votes
1answer
40 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
109 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?
2
votes
1answer
55 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$ ...
2
votes
1answer
157 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
51 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
133 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
50 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 ...
2
votes
2answers
90 views

If $x_1^3+x_2^3+\ldots+x_t^3=2002^{2002}$, find minimum value of $t$ so the condition can be satisfied by some natural numbers $x_i$

If $x_1^3+x_2^3+\ldots+x_t^3=2002^{2002}$, find the minimum value of $t$ so the condition can be satisfied by some natural numbers $x_i$. My attempt: I took modulo $9$ on both sides and found the ...
0
votes
2answers
48 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
53 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
91 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
51 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 ...
5
votes
2answers
402 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
45 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
78 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
62 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 ...
1
vote
1answer
45 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
71 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 not have an element of order $q$. Let $\zeta$ be an imaginary number whose order is ...
1
vote
1answer
63 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 ...
3
votes
0answers
72 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 ...
11
votes
1answer
225 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
1answer
33 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
105 views

The product of three consecutive natural numbers is divisible by $6$

Please give me feedback for my answer to this question. Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by $6$ My answer: True. Suppose $n$ is ...
2
votes
1answer
34 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 ...
1
vote
1answer
28 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
49 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
26 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
32 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 ...
7
votes
2answers
138 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
106 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
72 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
632 views

Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$

Can we prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$ and if so, which formulas can be used while proving?
8
votes
2answers
299 views

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

Prime $p\equiv3\pmod4$, then diophantine equation $$ |x^2-py^2|=\frac{p-1}{2} $$ has a solution in integers en, $x^2-py^2=-1$ has no solution in integers. I'd be grateful for any help you are ...
1
vote
0answers
32 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
98 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 ...
7
votes
1answer
139 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.
5
votes
4answers
427 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 ...
2
votes
1answer
85 views

Induction: Sum of the squares of 6 consecutive natural numbers

Define for every natural n: $$ a_{n}=\sum\limits_{i=0}^{5}(n+i)^2$$ in other words, $\ a_n$ is the sum of the squares of 6 consecutive natural numbers, the first number is $n^2$ and the last is ...
1
vote
1answer
50 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
100 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
133 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 ...