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

learn more… | top users | synonyms

0
votes
0answers
9 views

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 positive real $x_is$

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 positive real $x_is$. My attempt: I took modulo $9$ on both sides ...
0
votes
3answers
21 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
68 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
12 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 ...
3
votes
0answers
22 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
16 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
1answer
28 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
0answers
33 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
28 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
38 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
33 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
17 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
33 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 ...
9
votes
0answers
71 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
14 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
116 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
22 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
21 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
1answer
34 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
17 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
29 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
91 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
74 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
47 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
557 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
40 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, $ x^2-py^2 = -1 $ has no solution in integers. How about this problem? Thanks in ...
1
vote
0answers
29 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
12 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
55 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
346 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
42 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
75 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
97 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
29 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
35 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 ...
0
votes
1answer
32 views

Word problem number theory

The number of the students of one school is a natural number that is between $600$ and $500$. If we were to divide the students into $20$ groups or $12$ groups or $36$ groups, we get a remainder of ...
2
votes
3answers
67 views

Find the remainder of $40^{314}$ divided by 91.

Here's what I have so far. $$x \equiv 40^{314} \mod{91}$$ $$\Rightarrow$$ $$x \equiv 40^{314} \mod{7}$$ $$ x \equiv 40^{314} \mod{13}$$ Then by FLT, $$40^6 ≡ 1 \mod{7}$$ $$40^{12} ≡ 1 \mod{13}$$ ...
0
votes
0answers
17 views

Like Carmichael numbers

Given a positive integer $n$ which has a property : $A^n-A$ is divisible by $n$ for all $A\in$ {$2015,2016,2017,...,2014^2-1,2014^2$} . Show that $GCD(k^n-k,n)>1$ for all $k\in ...
0
votes
1answer
12 views

Optimal strategy in Euclid's game

Euclid's game (also known as the Game of Euclid) is played as follows: the players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from ...
1
vote
1answer
37 views

Concerning squarefree numbers with 2 primes and squarefrees with 3 primes.

If a squarefree with two primes is a 2-prime and a squarefree with three primes is a 3-prime is there an integer N such that the number of 2-primes less than N is equal to the number of 3-primes less ...
0
votes
1answer
19 views

Let $m=p^t$ where p is a prime. Prove that $a^{\phi(m)+t} \equiv a^t \bmod{m}$ for ${\bf all}$ integers a

So, I was thinking that $a^{\phi(m)}\equiv 1 \bmod{m}$, thus when multiplying $a^t$ on both sides, we get that $a^{\phi(m)+t} \equiv a^t \bmod{m}$. What is throwing me off is the all integers a part.
3
votes
1answer
35 views

$4|(p-1) \implies$ there is an element $x$ of order $ 4$ modulo $p$.?

"$p \equiv 1 \mod 4 \implies 4 \mid (p-1) \implies$ there is an element $x$ of order $4$ modulo $p$." I am having a difficult time understanding why this implies there is an element $x$ of order $4$. ...
0
votes
0answers
31 views

Summatory Function $F(n) = 1 $ for all $n$ odd, and $F(n) = 2$ for all n even

So, I have this summatory function $$ F(n)=\sum_{d\mid n}f(n)$$ that goes $F(n) = 1$ for $2\nmid n$, and $F(n)=2$ for $2\mid n$. This summatory function is multiplicative. I need to describe the ...
4
votes
4answers
80 views

Prove that $a^7-a$ is divisible by 168 when a is odd

so I saw a similar question that proves $168\mid(a^6-1)$ when $(42,a) = 1$. But for this problem I was not given that gcd$(a,42)=1$. When I factor out a I get $168\mid a\cdot(a^6 - 1)$ and since $a$ ...
0
votes
1answer
17 views

Prove that if d = gcd(m,n) then $\phi(mn)=\phi(m)*\phi(n)/d$ [duplicate]

So if m and n are relatively prime, then the $\phi(mn)=\phi(m)*\phi(n)$ but what happens when $d > 1$?
3
votes
4answers
26 views

Least positive residue of $10! mod 143$

So I got that $10! \equiv 10\ (\textrm{mod}\ 11)$ and $10! \equiv 9\ (\textrm{mod}\ 13)$ but I am not sure how to apply the chinese remainder theorem to arrive at the solution for $x \equiv 10!\ ...
0
votes
0answers
24 views

In $Z/3Z[x]$ find the GCD of $x^5+2x^3+x^2+x+1$ and $x^4+2x^3+x+1$

I know that to do this, I use Euclid's algorithm. So in my first step, I got the following: $x^5+2x^3+x^2+x+1=(x^4+2x^3+x+1)(x+1)+(2x)$. So in the next step, I divide $(x^4+2x^3+x+1)$ by the remainder ...