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

learn more… | top users | synonyms

0
votes
1answer
17 views

Totient and division

I know that if the arguments are relatively prime, I can write $$ \phi(ab)=\phi(a)\phi(b) $$ can I conclude that if $b\mid a$ $$ \frac{\phi(a)}{\phi(b)}=\phi(\frac{a}{b}) $$ Thanks
1
vote
0answers
15 views

What is the period of this sequence?

Consider the recurrence relation: $x_{i+1}=p-1-((p*i-1) \text{ % }x_i)$ If $p$ is prime and $x_0=1$, what is the least period of the resulting (eventually periodic) sequence? My guess is the ...
2
votes
1answer
46 views

Number of palindromic numbers less than a power of $10$

I noticed that every $10^{n}$ there is a certain number of palindromic numbers that I collected in this sequence: $$S=\{a_n,a_{n+1},a_{n+2}...\}=\{10,9,90,90,900,900...\}$$ where every number $a_n$ is ...
0
votes
0answers
17 views

Program for Handling Huge Primes

I am trying to run a program with really large primes (around the $10^{20}$th prime), but Mathematica seems to only be able to handle around the first $10^{12}$ primes. Is there any software that can ...
1
vote
1answer
22 views

Question on Cardinality ..Help

a) Let $n$ be a positive integer. Define a relation on $\mathbb{Z} $, which yields a partition of $\mathbb{Z}$ with $n$ elements; and give the partition. b) Deduce that $n\omega = \omega$ where ...
1
vote
0answers
32 views

Proof that if 'a' and 'b' can be written as sum of two squares then so can lcm[a,b]

Firsty if a and b can be written as the sum of two squares, then there exists no odd power in either prime factorisation of the form 4k+3. If this is the case and the lcm[a,b] is the common prime ...
1
vote
1answer
27 views

Modular arithemtic and CRT

I'm trying to solve the following congruence: $71x-1 \equiv 0 \pmod{59367} $ Given that $59367=771 \times 77$, I have previously solved that: $71x \equiv 1 \pmod{771}$ such that $x=-76$ $71x ...
1
vote
1answer
39 views

How to find the LCM sum function? lcm(1,n) + lcm(2,n) + … lcm(n,n)

given an integer n, How do we find S=lcm(1,n) + lcm(2,n) +... lcm(n,n). I know how find the gcd(1,n) + gcd(2,n) +...gcd(n,n) . Because there is phi(n) + sum{phi(n/i) * i} where i|n. But how do I use ...
12
votes
1answer
268 views

A fascinating number chain.

Take a two digit number $10x+y$ of which both digits are different. now add $y-x$ to this number. By repeating this process you will get a chain of numbers $45,46,48,52,49,54,53,51,47,50.$ after $50, ...
2
votes
1answer
37 views

Proof that $n$ is prime when $1+x+x^2+…+x^{n-1}$ = ${1-x^n}\over{1-x}$ is prime.

Given $x$ and $n$ are positive integers and $1+x+x^2+...+x^{n-1}$ is a prime number. Then prove that $n$ is a prime number. Can the formula $1+x+x^2+...+x^{n-1} = \dfrac{1-x^n}{1-x}$ be somehow used? ...
0
votes
0answers
20 views

Combinations and Permutations. integer solutions

(a) How many integer solutions are there to the equation $x + y + z = 15$ if (i) $x$, $y$, $z$ are non-negative? (ii) $x$, $y$, $z$ are positive? (iii) $x$, $y$, $z$ are non-negative and $z \leq 5$? ...
0
votes
0answers
20 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
34 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$?
1
vote
3answers
60 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.: ...
4
votes
1answer
40 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$.
0
votes
1answer
15 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
33 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
44 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
202 views

Why irrational implies having an infinite decimal expansion?

Why irrational means having an infinite decimal expansion?
0
votes
1answer
21 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
62 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
21 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
31 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
37 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
81 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
22 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
13 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
61 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
49 views
+50

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
19 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
41 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
52 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
35 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
45 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
48 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
92 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
123 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 ...